There are $n$ chairs in a row, initially all unmarked.

You are given a permutation $p$$^{\text{∗}}$ of length $n$.

Now, you play a game. You visit each chair sequentially, starting from the $1$-st chair. At the $i$-th chair, you can do the following:

• If the $i$-th chair is already marked, then you end the game immediately without sitting on it.
• Otherwise, you can choose to sit on the chair or skip it and move to the next chair.
• If you choose to sit on the chair, then after standing up, you mark the $p_i$-th chair and move to the next chair.

If all the $n$ chairs are visited, the game ends.

Your task is to determine the maximum number of chairs that you can sit on.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of chairs.

The second line of each test case contains $n$ distinct integers $p_1, p_2,\ldots,p_{n}$ — the permutation $p$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

Output

Output a single integer — the maximum number of chairs you can sit on.

Note

In the first test case, you can proceed as follows:

1. You visit the $1$-st chair, sit on it, and mark the $3$-rd chair.
2. You visit the $2$-nd chair, sit on it, and mark the $2$-nd chair.
3. You visit the $3$-rd chair. Since it is marked, you end the game.

Therefore, using this sequence, you can sit on a total of $2$ chairs. It can be shown that the maximum number of chairs using any sequence of moves is $2$.

In the second test case, you can proceed as follows:

1. You visit the $1$-st chair, sit on it, and mark the $4$-th chair.
2. You visit the $2$-nd chair and skip it.
3. You visit the $3$-rd chair, sit on it, and mark the $2$-nd chair.
4. You visit the $4$-th chair. Since it is marked, you end the game.

Therefore, using this sequence, you can sit on a total of $2$ chairs. It can be shown that the maximum number of chairs using any sequence of moves is $2$.

Samples

4
3
3 2 1
5
4 3 2 5 1
4
4 2 1 3
4
2 3 4 1

2
2
3
1