本题没有可用的提交语言。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem C. Construction, I am a Master of it!

Input file:　standard input
Output file:　standard output
Time limit:　1 second
Memory limit:　256 megabytes

众所周知，$\mathtt{MEX}$ (Minimum Excluded) 问题在 $\mathtt{codeforces}$ 平台上随处可见，考虑到其出色的思维性，Ocean 决定考考最近正在刷构造题的大师黄神。

我们约定 $\text{MEX}(a, b, c, \ldots)$ 为不出现在 $a, b, c, \ldots$ 中的最小非负整数。

如 $\text{MEX}(3, 2, 1, 0) = 4, \text{MEX}(1, 1, 4, 5, 1, 4) = 0, \text{MEX}(0, 6, 1, 6) = 2$。

Ocean 给了黄神一个长为 $n$ 的序列 $a$，希望黄神给出一种构造方案，让 $\text{MEX}(a_1 + a_2, a_2 + a_3, \ldots ,a_{n - 1} + a_n)$ 最小。

有趣的是，Ocean 允许黄神在计算前，将 $a$ 按照任意方式重新排序。

显然，黄神一眼就秒了这题，光速扔给 Ocean 一个构造方案。虽然是意料之内，但 Ocean 好奇，你会不会做这题。

考虑到你可能不是构造大师，所以 Ocean 打算只让你告诉他最后的结果即可。你能回答他么？

Input

本题有多组测试用例。

第一行给定一个整数 $t$ $(1 \leq t \leq 10 ^ 4)$，代表测试用例的数量。

接下来，对于每个测试用例：

第一行给定一个整数 $n$ $(2 \leq n \leq 2 \times 10 ^ 5)$，代表序列 $a$ 的长度。

第二行包含 $n$ 个整数，第 $i$ 个整数代表 $a_i$ $(0 \leq a_i \leq 2 \times 10 ^ 5)$ 的值。

保证所有样例的 $n$ 总和不超过 $2 \times 10 ^ 5$。

Output

对于每组测试用例，输出一个整数，代表任意排序后 $\text{MEX}(a_1 + a_2, a_2 + a_3, \ldots ,a_{n - 1} + a_n)$ 的最小值。

Example

Hint

在第一个测试用例中，将 $a$ 重新排列为 $[0,0]$ 是最优的，此时结果为 $[0+0]=[0]$ 的 $\text{MEX}$，即 $1$ 。

在第二个测试用例中，将 $a$ 重新排列为 $[0,1,0]$ 是最优的，此时结果为 $[0+1,1+0]=[1,1]$ 的 $\text{MEX}$，即 $0$ 。