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

MEX Destruction

Examples