Consider a Permutation $P$ of length $N$.

Let us define an operation on $P$ as follows:

• $P[i] = P[P[i]]$     $\forall$ $i$ from $1$ to $N$.

For example

Let initially $P = [2\ 3\ 1]$

So, $P[1] = 2, P[2] = 3, P[3] = 1$

After $1$ operation:

 $P[1]$ becomes $P[P[1]] = P[2] = 3$

 $P[2]$ becomes $P[P[2]] = P[3] = 1$

 $P[3]$ becomes $P[P[3]] = P[1] = 2$

 So, $P$ becomes $[3\ 1\ 2]$

You need to find the minimum number of operations after which $P$ becomes an Identity Permutation.

Output $-1$ if not possible.

Note

• Identity Permutation is $1, 2, 3 \dots N$

Input Format

• The First line contains an integer $T$ representing the number of test cases.
• Each test case contains an integer $N$ representing the size of permutation $P$.
• Next line contains $N$ space seperated integers representing the permutation $P$.

Output Format

• For each test case, Print the minimum number of operations as asked, output $-1$ if not possible.

Constraints

• $1 \le T \le 5$
• $1 \le N \le 10^6$
• $1 \le P[i] \le N$