Question
Permutation Disturbance
Rahul likes to create disturbance in numbers. In other words, he does not like when numbers are in their right positions.
He has a permutation P of size N. In one operation, he can swap any two adjacent elements.
His goal is to alter the permutation in such a way that Pi ≠ i satisfies for all 1 ≤ i ≤ N.
Help Chef find the minimum number of operations required to reach his goal.
Note that a permutation of size N is a sequence of integers consisting of all integers from 1 to N exactly once.
Input
The first line of the input contains a single integer T, denoting the number of test cases.
The first line of each test-case contains a single integer N, denoting the number of elements.
The second line of each test-case contains N space-separated integers, denoting the elements of an array.
Constraints
1 ≤ T ≤ 104
2 ≤ N ≤ 105
It is guaranteed that P denotes a permutation.
Note: The sum of N over all test cases won't exceed 105.
The first line of each test-case contains a single integer N, denoting the number of elements.
The second line of each test-case contains N space-separated integers, denoting the elements of an array.
Constraints
1 ≤ T ≤ 104
2 ≤ N ≤ 105
It is guaranteed that P denotes a permutation.
Note: The sum of N over all test cases won't exceed 105.
Output
For each test case, output on a new line, the minimum number of operations required by Rahul to reach his goal.
Example
Sample Input
3
3
3 1 2
2
1 2
4
3 2 1 4
Sample Output
0
1
2
Explanation
Test case 1: Each element in the permutation already satisfies the condition, hence
0.
Test case 2: After swapping the two elements in one operation, both satisfy the condition.
3
3
3 1 2
2
1 2
4
3 2 1 4
Sample Output
0
1
2
Explanation
Test case 1: Each element in the permutation already satisfies the condition, hence
0.
Test case 2: After swapping the two elements in one operation, both satisfy the condition.