You are given permutation of N integers, that is, every number from 1 to N appears exactly once in the array. What is minimal number of swaps needed to sort the array?

Constraints

N <= 100

Input

First number in the input is number t (t <= 100), denoting the number of test cases. Every test case looks as follows. First line is number N describing size of the array. N number follow, denoting the array.

Output

Output one number, minimal number of swaps.

Example

Input:
2
3
2 1 3
5
5 3 4 2 1

Output:
1
3

Explanation

In the first case, we swap (1, 2). In second example, we swap (5,1), (3,2), (4,3).