Description

Christmas is coming. Now $n$ kids in the Xifeng Huhu Welfare Home are going to exchange gifts.

Before that, every kid has prepared a gift and so there are $n$ gifts in total. For convenience, we number the kids from $1$ to $n$, and the gift prepared by the $i$-th kid is also numbered $i$ ($i=1,2,\ldots ,n$).

Initially, every kid will have a gift randomly selected from all of the gifts, and then they sit in a circle around the Christmas tree in the order of number $1$ to $n$ clockwise. (It means, kids with number $1$ and $n$ are adjacent.) Then they will start to exchange gifts. Each time for exchange, every kid will give the gift in his hands to the kid sitting on his left and take the gift given by the kid sitting on his right. To be specific, assuming that after $k$ times of exchange, the number of the gift in the $i$-th kid's hands is $a_{k,i}$, then after the $(k+1)$-th exchange, $a_{k+1,i}=a_{k,i-1}$. Specially, $a_{k+1,1}=a_{k,n}$.

For example, if there are three kids, and the number of the gifts in their hands initially is $2,1,3$ respectively, then after the first time of exchange, the number of the gifts in their hands will become $3,2,1$ respectively.

However, kids don't want to get gifts prepared by themselves, so they wonder how many times they should exchange their gifts at least (possibly $0$), so that every kid will have a gift not prepared by himself. That is, for every $i$ from $1$ to $n$, $a_i\neq i$ holds. Here, $a_i$ represents the number of the gift in the $i$-th kid's hands.

Input

The input consists of multiple test cases. The first line contains a single integer $t$ $(1\leq t\leq 10^5)$, indicating the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(2\leq n\leq 2\cdot 10^5)$, indicating the number of the kids.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots ,a_n$ $(1\leq a_i\leq n)$, indicating the number of the gift in the $i$-th kid's hands initially. It's guaranteed that every number from $1$ to $n$ appears exactly once.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, print a line containing a single integer $k$, denoting that at least $k$ times of exchange should be performed in order to achieve the requirement.

If such $k$ doesn't exist, print $-1$.

Samples

2
3
2 1 3
5
1 5 4 2 3

-1
2

3
5
2 3 5 1 4
7
4 2 6 3 1 5 7
10
7 3 1 6 2 4 10 8 9 5

0
1
4

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛