给你一个长度为$$$n$$$的数组$$$a$$$。 $$$a$$$ 的分数是 $$$[a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n]$$$ 的 MEX$$$^{\dagger}$$$。如果允许您以任意顺序重新排列 $$$a$$$ 的元素,请求 $$$a$$$ 的最低分数。请注意,您不需要构建达到最低分数的数组 $$$a$$$。
$$$^{\dagger}$$$ 数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如:
- $$$[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$$$ 不属于该数组。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,以任意顺序重新排列 $$$a$$$ 的元素后输出 $$$a$$$ 的最低分数。
示例
输入 #1
3 2 0 0 3 0 0 1 8 1 0 0 0 2 0 3 0
输出 #1
1 0 1
注意
在第一个测试用例中,最好将$$$a$$$重新排列为$$$[0,0]$$$,该数组的分数是$$$[0+0]=[0]$$$的MEX,即$$$1$$$。
在第二个测试用例中,最好将$$$a$$$重新排列为$$$[0,1,0]$$$,该数组的分数是$$$[0+1,1+0]=[1,1]$$$的MEX,即$$$0$$$。