Before distributing the kingdom, Julius thought to take the test of princes to make a king. Julius thought to give them a sequence of n distinct numbers from 0 to n - 1. Now he told them that if a[i] = i, then i is our soldier.

For example, array [0, 2, 1] has 1 soldier and array [0, 1, 2] has 3 soldier. Caesar also added that if any two soldier are not at their places i.e. a[i] is not equal to i than he could swap the two positions such that the number of soldier can be increased in the army. Note that the princes can swap the position at most once. So the king ask the prince to tell the maximum number of the soldiers in the army.

Input

The input first line contains the number of test cases t (1 <= t <= 100) and than the next line contains the total number of elements n (1 <= n <= 10^5) in the sequence and than the next line contains n integers a0, a1 ... an.

Output

Print the t lines that contains the answer to the above problem.

Example

Input:
1
5
0 1 3 4 2

Output:
3