← 返回题目列表

Codeforces · 1926/D

D. 弗拉德和师

中文机器翻译题面 查看原题

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$$$(含)。