310258: CF1806B. Mex Master

B. Mex Mastertime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExampleInput

3
2
0 0
3
0 0 1
8
1 0 0 0 2 0 3 0

Output

1
0
1

Note

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

题目大意：
给定一个长度为n的数组a。数组a的得分是数组[a1+a2, a2+a3, …, an-1+an]的MEX值。求出允许重新排列a数组元素顺序后的最小得分。注意，不需要构造出达到最小得分的数组a。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。
每个测试用例的第一行包含一个整数n（2≤n≤2×10^5）。
每个测试用例的第二行包含n个整数a1, a2, …, an（0≤ai≤2×10^5）。
保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出重新排列数组a元素顺序后的最小得分。

示例：
输入：
3
2
0 0
3
0 0 1
8
1 0 0 0 2 0 3 0

输出：
1
0
1

说明：
在第一个测试用例中，最优的排列方式是[0,0]，该数组的得分是数组[0+0]=[0]的MEX值，即1。
在第二个测试用例中，最优的排列方式是[0,1,0]，该数组的得分是数组[0+1,1+0]=[1,1]的MEX值，即0。题目大意： 给定一个长度为n的数组a。数组a的得分是数组[a1+a2, a2+a3, …, an-1+an]的MEX值。求出允许重新排列a数组元素顺序后的最小得分。注意，不需要构造出达到最小得分的数组a。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含一个整数n（2≤n≤2×10^5）。 每个测试用例的第二行包含n个整数a1, a2, …, an（0≤ai≤2×10^5）。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出重新排列数组a元素顺序后的最小得分。 示例： 输入： 3 2 0 0 3 0 0 1 8 1 0 0 0 2 0 3 0 输出： 1 0 1 说明： 在第一个测试用例中，最优的排列方式是[0,0]，该数组的得分是数组[0+0]=[0]的MEX值，即1。 在第二个测试用例中，最优的排列方式是[0,1,0]，该数组的得分是数组[0+1,1+0]=[1,1]的MEX值，即0。