Evirir the dragon snuck into a wizard's castle and found a mysterious contraption, and their playful instincts caused them to play with (destroy) it...

Evirir the dragon found an array $a_1, a_2, \ldots, a_n$ of $n$ non-negative integers.

In one operation, they can choose a non-empty subarray$^{\text{∗}}$ $b$ of $a$ and replace it with the integer $\operatorname{mex}(b)$$^{\text{†}}$. They want to use this operation any number of times to make $a$ only contain zeros. It can be proven that this is always possible under the problem constraints.

What is the minimum number of operations needed?

$^{\text{∗}}$An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

$^{\text{†}}$The minimum excluded (MEX) of a collection of integers $f_1, f_2, \ldots, f_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $f$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 200$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 50$), the length of $a$.

The second line of each test case contains $n$ space-separated integers, $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 100$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

Output

For each test case, output a single integer on a line, the minimum number of operations needed to make $a$ contain only zeros.

Note

In the first test case, Evirir can choose the subarray $b = [1, 2, 3]$ and replace it with $\operatorname{mex}(1, 2, 3) = 0$, changing $a$ from $[0, \underline{1, 2, 3}]$ to $[0, 0]$ (where the chosen subarray is underlined). Therefore, the answer is $1$.

In the second test case, $a$ already contains only $0$s, so no operation is needed.

In the third test case, Evirir can change $a$ as follows: $[1, \underline{0, 1, 0, 1}] \to [\underline{1, 2}] \to [0]$. Here, $\operatorname{mex}(0, 1, 0, 1) = 2$ and $\operatorname{mex}(1, 2) = 0$.

In the fourth test case, Evirir can choose $b$ to be the entire array $a$, changing $a$ from $[\underline{3, 1, 4, 1, 5}]$ to $[0]$.

Samples

10
4
0 1 2 3
6
0 0 0 0 0 0
5
1 0 1 0 1
5
3 1 4 1 5
4
3 2 1 0
7
9 100 0 89 12 2 3
4
0 3 9 0
7
0 7 0 2 0 7 0
1
0
2
0 1

1
0
2
1
1
2
1
2
0
1