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]$.
样例
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
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。