B. Simply Sitting on Chairs
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
4
3
3 2 1
5
4 3 2 5 1
4
4 2 1 3
4
2 3 4 1
Output
2
2
3
1
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$$$.