RIOI_0_1 - Order

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).


Added by:Buda IM
Date:2012-10-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Known problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.