The direction the compass points to / The direction the compass points to Is where the heart desires / Is where the heart desires

Yuki has a sequence $a$ of length $n$.

Yuki defines a "Fish-Fish" operation as follows:

• Choose two integers $l$ and $r$ such that $1 \le l \le r \le n$.
• Let $x$ be the $\operatorname{mex}$ of the subsequence $a_l \sim a_r$. Delete all elements in $a_l \sim a_r$ that are greater than $x$, and update $n$ to the new length of the sequence $a$.

You need to find the minimum number of "Fish-Fish" operations required to make the sequence $a$ as short as possible.

In this problem, the $\operatorname{mex}$ of a sequence is the smallest non-negative integer that does not appear in the sequence. For example:

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

Specifically, when the sequence is empty, its $\operatorname{mex}$ is $0$.

Input

This problem contains multiple test cases.

The first line of input contains two integers $c$ and $t$, representing the subtask ID and the number of test cases, respectively. The sample satisfies $c=0$.

Each test case is then provided as follows:

• The first line contains an integer $n$.
• The second line contains $n$ integers $a_1, \dots, a_n$.

Output

For each test case, output a single integer representing the minimum number of "Fish-Fish" operations required to make the sequence $a$ as short as possible.

Examples

Input 1

0 5
4
2 0 2 6
5
1 0 3 3 1
5
1 1 8 3 1
6
1 0 3 1 0 2
7
4 0 9 8 1 3 8

Output 1

1
2
1
3
2

Note

For the first test case, choosing $l=1$ and $r=n$ for the "Fish-Fish" operation makes the sequence $a$ become $\{0\}$. It is easy to prove that $0$ cannot be deleted, so the length of the sequence $a$ reaches its minimum.

For the second test case, one can first choose $l=1$ and $r=1$ for the "Fish-Fish" operation, making the sequence $a$ become $\{0, 3, 3, 1\}$. Then, choose $l=2$ and $r=4$ for the "Fish-Fish" operation, making the sequence $a$ become $\{0\}$, reaching the minimum length.

Constraints

Let $\sum n$ denote the sum of $n$ over a single test case.

For all test cases:

• $1 \le t \le 10^5$
• $1 \le n \le 5 \cdot 10^5$, $\sum n \le 5\cdot 10^5$
• $0 \le a_i \le 10^9$ for all $1 \le i \le n$

This problem uses bundled testing.

• Subtask 1 (18 points): $n \le 10$, $\sum n \le 10$.
• Subtask 2 (5 points): The sequence $a$ is guaranteed not to contain $0$.
• Subtask 3 (21 points): The sequence $a$ is guaranteed to contain exactly one $0$.
• Subtask 4 (24 points): $a_i=0$ for all positive odd integers $i \le n$.
• Subtask 5 (32 points): No special constraints.