D. Влад и разделение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Владислава есть $$$n$$$ неотрицательных целых чисел, и он хочет разделить их все на несколько групп так, чтобы в любой группе любая пара чисел не имела совпадающих значений битов среди битов от $$$1$$$-го до $$$31$$$-го (то есть рассматриваем $$$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$$$ в группе должно выполняться условие $$$x_2(i) \neq y_2(i)$$$ для всех $$$1 \leq i < 32$$$.

Какое минимальное количество групп Владу нужно, чтобы достичь своей цели? Каждое число должно попасть ровно в одну группу.

Входные данные

Первая строка содержит одно целое число $$$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$$$.

Выходные данные

Для каждого теста выведите одно целое число  — минимальное количество групп, необходимое для удовлетворения условия.

Пример
Входные данные
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
Выходные данные
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)$$$ для всех $$$i$$$ от $$$1$$$ до $$$31$$$, включительно.