CF1806B.Mex Master

You are given an array $a$ of length $n$ . The score of $a$ is the MEX $^{\dagger}$ of $[a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n]$ . Find the minimum score of $a$ if you are allowed to rearrange elements of $a$ in any order. Note that you are not required to construct the array $a$ that achieves the minimum score.

$^{\dagger}$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of $[2,2,1]$ is $0$ , because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$ , because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$ because $0$ , $1$ , $2$ , and $3$ belong to the array, but $4$ does not.

The first line contains a single integer $t$ ( $1\le t\le 10^4$ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ( $2\le n\le 2\cdot10^5$ ).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 2\cdot 10^5$ ).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$ .

For each test case, output the minimum score of $a$ after rearranging the elements of $a$ in any order.

In the first test case, it is optimal to rearrange $a$ as $[0,0]$ , the score of this array is the MEX of $[0+0]=[0]$ , which is $1$ .

In the second test case, it is optimal to rearrange $a$ as $[0,1,0]$ , the score of this array is the MEX of $[0+1,1+0]=[1,1]$ , which is $0$ .