It is Prof. Honeygrahi's favourite time of the semester - end-sems. There are N students in his class and they are seated in one long row to take the dreaded algorithms end-semester examination. The seats are numbered left to right from 1 to N. However, Honeygrahi is apprehensive about cheating in the examination and hence rearranges the students according to a fixed rule R.

R is nothing but a permutation of numbers 1,2,....,N. eg. a rule for N = 3 could be (1,3,2). The rule is to be interpreted as follows - if the ith number of the rule is j, it means that the student sitting on the jth seat goes to the ith seat. Here, the student on seat-1 stays where she is. Students on seats 2 and 3 interchange their positions.

Now, Honeygrahi becomes so paranoid about cheating that he frantically keeps applying the same rule over and over again. He does not realize that he may end up with the original arrangement!

You are a student who likes the original arrangement, and hence wants to know the minimum number of times the rule has to be applied to restore the original arrangement. The rule has to be applied at-least once.

INPUT:

First line of input contains the number of test cases T. T test cases follow.

The first line of each test case contains the number of students N. The second line of each test case contains N space separated integers which is a rearrangement of the numbers 1,2,..,N. This is the rule R.

OUTPUT:

For each test case, print the minimum number of times the rule has to be applied again and again to restore the original arrangement. If it is not possible to restore the original arrangement, print -1.

CONSTRAINTS:

1 <= T <= 1000

1 <= N <= 1000

NOTE: It is guaranteed that the answer does not exceed 10^15.

PROBLEM SETTER: Siddharth Ancha