Equal Mex Splitting ~ Multiplex Coder

Chef has an array

$A$ of length $N$ . Chef wants to select some disjoint, non-empty subarrays from $A$ such that:

The $m e x$ of each of the selected subarray is the same.

Note that the selected subarrays need not cover all the elements of the array.

For e.g. if $A = [2, 0, 1, 6, 2, 1, 3, 0, 7]$ , then one way in which Chef can select subarrays is as following: $[0, 1], [1, 3, 0]$ (Here $m e x$ of both of them is $2$ ).

Chef wants to select the maximum number of disjoint, non-empty subarrays that satisfy the above condition. Can you help him to do so?

Note: An array $X$ is called a subarray of an array $Y$ if $X$ can be obtained from $Y$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Also, $m e x$ of a subarray is the smallest non-negative number that does not occur in that subarray.

Input Format

The first line will contain $T$ - the number of test cases. Then the test cases follow.
The first line of each test case contains a single integer $N$ - the length of the array $A$ .
The second line of each test case contains $N$ space-separated integers - $A_{1}, A_{2}, \dots, A_{N}$ denoting the array $A$ .

Output Format

For each test case, output the maximum number of disjoint subarrays which Chef can select such that $m e x$ of each subarray is the same.

Constraints

$1 \leq T \leq 1000$
$1 \leq N \leq 10^{5}$
$0 \leq A_{i} \leq N$
It is guaranteed that the sum of $N$ does not exceed $5 \cdot 10^{5}$

Sample Input 1

2
4
0 1 1 0
6
0 0 3 1 2 0

Sample Output 1

2
3

Explanation

Test case-1: Chef can select the following subarrays: $[0, 1]$ , $[1, 0]$ . Here $m e x ([0, 1]) = m e x ([1, 0]) = 2$ . Therefore the answer is $2$ .

Test case-2: Chef can select the following subarrays: $[0]$ , $[0, 3]$ , $[2, 0]$ . Here $m e x ([0]) = m e x ([0, 3]) = m e x ([2, 0]) = 1$ . Therefore the answer is $3$ .