Vladislav 有 $$$n$$$ 个非负整数,他想将它们全部分成几个组,以便在任何组中,任何数字对在 $$$1$$$-st 到 $$$31$$$-st 位之间没有匹配的位值(即,考虑二进制表示的 $$$31$$$ 最低有效位)。
对于整数 $$$k$$$,让 $$$k_2(i)$$$ 表示其二进制表示中的第 $$$i$$$ 位(从右到左,索引从 1 开始)。例如,如果 $$$k=43$$$,由于 $$$43=101011_2$$$,则 $$$43_2(1)=1$$$、$$$43_2(2)=1$$$、$$$43_2(3)=0$$$、$$$43_2(4)=1$$$、$$$43_2(5)=0$$$、 $$$43_2(6)=1$$$、$$$43_2(7)=0$$$、$$$43_2(8)=0、\dots、43_2(31)=0$$$。
形式上,对于同一组中的任意两个数字 $$$x$$$ 和 $$$y$$$,对于所有 $$$1 \leq i < 32$$$,条件 $$$x_2(i) \neq y_2(i)$$$ 必须成立。
Vlad 需要多少组才能实现他的目标?每个数字必须恰好属于一组。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 整数总数。
每个测试用例的第二行包含 $$$n$$$ 给定整数 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_j < 2^{31}$$$)。
测试中所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 满足条件所需的最小组数。
示例
输入 #1
9 4 1 4 3 4 2 0 2147483647 5 476319172 261956880 2136179468 1671164475 1885526767 3 1335890506 811593141 1128223362 4 688873446 627404104 1520079543 1458610201 4 61545621 2085938026 1269342732 1430258575 4 0 0 2147483647 2147483647 3 0 0 2147483647 8 1858058912 289424735 1858058912 2024818580 1858058912 289424735 122665067 289424735
输出 #1
4 1 3 2 2 3 2 2 4
注意
在第一个测试用例中,任何两个数字都有相同的最后 $$$31$$$ 位,因此我们需要将每个数字放在自己的组中。
在第二个测试用例中, $$$a_1=0000000000000000000000000000000_2$$$, $$$a_2=1111111111111111111111111111111_2$$$ 因此它们可以放在同一组中,因为$$$a_1(i) \ne a_2(i)$$$ 对于 $$$1$$$ 和 $$$31$$$ 之间的每个 $$$i$$$(含)。