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$$$.

$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

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$$$.

Note

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 \lt 4$$$. However, the subsequence $$$[4, 3, 2, 1, 0]$$$ of this sequence is magical, so the answer is $$$5$$$.

White Magic

Examples