We call a sequence $a_1, a_2, \ldots, a_n$ magical if for all $1 \leq i \leq n-1$ it holds that: $\operatorname{min}(a_1, \ldots, a_i) \geq \operatorname{mex}(a_{i+1}, \ldots, a_n)$. In particular, any sequence of length $1$ is considered magical.

The minimum excluded (MEX) of a collection of integers $a_1, a_2, \ldots, a_k$ is defined as the smallest non-negative integer $t$ which does not occur in the collection $a$.

You are given a sequence $a$ of $n$ non-negative integers. Find the maximum possible length of a magical subsequence$^{\text{∗}}$ of the sequence $a$.

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 an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the sequence $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the elements of the sequence $a$.

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

Output

For each test case, output a single number — the maximum possible length of a magical subsequence of the sequence $a$.

见题面 Input 部分

见题面 Output 部分

In the first test case, the sequence $[4, 3, 2, 1, 0]$ is magical, since:

• $\operatorname{min}(4) = 4, \operatorname{mex}(3, 2, 1, 0) = 4$. $4 \geq 4$
• $\operatorname{min}(4, 3) = 3, \operatorname{mex}(2, 1, 0) = 3$. $3 \geq 3$
• $\operatorname{min}(4, 3, 2) = 2, \operatorname{mex}(1, 0) = 2$. $2 \geq 2$
• $\operatorname{min}(4, 3, 2, 1) = 1, \operatorname{mex}(0) = 1$. $1 \geq 1$

In the second test case, the sequence $[4, 3, 3, 2, 1, 0]$ is not magical, since $\operatorname{min}(4, 3) = 3, \operatorname{mex}(3, 2, 1, 0) = 4$, $3 < 4$. However, the subsequence $[4, 3, 2, 1, 0]$ of this sequence is magical, so the answer is $5$.