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:

You visit the $$$1$$$-st chair, sit on it, and mark the $$$3$$$-rd chair.
You visit the $$$2$$$-nd chair, sit on it, and mark the $$$2$$$-nd chair.
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:

You visit the $$$1$$$-st chair, sit on it, and mark the $$$4$$$-th chair.
You visit the $$$2$$$-nd chair and skip it.
You visit the $$$3$$$-rd chair, sit on it, and mark the $$$2$$$-nd chair.
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$$$.

Simply Sitting on Chairs

Examples