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.

给你一个长度为 $n$ 的数组 $a$。数组 $a$ 的得分为数组 $[a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n]$ 的 MEX$^{\dagger}$。若允许你以任意顺序重排数组 $a$ 的元素，求 $a$ 可能的最小得分。注意：你无需构造出达到该最小得分的具体数组 $a$。

$^{\dagger}$ 数组的 MEX（minimum excluded，最小未出现值）是指不属于该数组的最小非负整数。例如：

• $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在该数组中。
• $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在该数组中，但 $2$ 不在。
• $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都在该数组中，但 $4$ 不在。

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

第一行包含一个整数 $t$（$1\le t\le 10^4$）——测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 2\cdot10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 2\cdot 10^5$）。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

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

对于每个测试用例，输出在以任意顺序重排数组 $a$ 的元素后，$a$ 的最小得分。

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

在第一个测试用例中，将 $a$ 重排为 $[0,0]$ 是最优的，该数组的得分为 $[0+0]=[0]$ 的 MEX，即 $1$。

在第二个测试用例中，将 $a$ 重排为 $[0,1,0]$ 是最优的，该数组的得分为 $[0+1,1+0]=[1,1]$ 的 MEX，即 $0$。