D. Deviously Disorganized Documents
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Om and Mo are rivals in the college application process, both applying to the prestigious Red Panda University.

Recently, after getting access to Om's document of $$$n$$$ essays (ordered $$$1$$$ through $$$n$$$), Mo decided to sabotage Om by duplicating and shuffling his essays. Since Om blindly copy-pastes his essays into Common App, the RPU admissions officers are sure to reject him!

Mo is in the middle of this process, when he finds out that there has been a complication. Om's parents just donated a building to RPU! Now, Om only needs one correctly ordered essay to get in. In other words, Om will be admitted if and only if $$$a_i=i$$$ for some $$$1 \le i \le n$$$.

In one operation, Mo can swap any two essays $$$a_i$$$ and $$$a_j$$$. How many operations does he need to perform to ensure Om does not get into RPU?

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^4$$$).

The first line of each test contains $$$n$$$, the number of essays in Om's document ($$$1 \le n \le 10^5$$$).

The second line of each test contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, the order of Om's essays ($$$1 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all tests does not exceed $$$10^5$$$.

Output

For each test, if Mo cannot prevent Om from getting admitted, output -1.

Otherwise, output the minimum number of operations he needs to perform to prevent Om from getting admitted.

Example
Input
4
5
1 5 3 2 4
3
1 1 1
3
1 2 3
2
2 1
Output
1
-1
2
0
Note

In the first test, $$$a_1 = 1$$$ and $$$a_3 = 3$$$ initially. We can swap $$$a_1$$$ and $$$a_3$$$ to get $$$a = [3,5,1,2,4]$$$, which satisfies $$$a_i \neq i$$$.

This takes $$$1$$$ operation, and we need at least one operation, so the answer is $$$1$$$.

In the second test, no matter what swaps we do, $$$a_1=1$$$.

In the third test, we can swap $$$a_1$$$ and $$$a_2$$$ to get $$$a=[2,1,3]$$$, then swap $$$a_2$$$ and $$$a_3$$$ to get $$$a=[2,3,1]$$$.

In the fourth test, note that the answer might already be achieved.