Problem: codeforces/2049A
Time limit: 1000 ms, Memory limit: 256 MB

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 Format

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 Format

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


Sample Input 1

```
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
```

Sample Output 1

```
1
0
2
1
1
2
1
2
0
1
```

Notes

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