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?

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.

见题面 Input 部分

见题面 Output 部分

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