311046: CF1926D. Vlad and Division

D. Vlad and Divisiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vladislav has $n$ non-negative integers, and he wants to divide all of them into several groups so that in any group, any pair of numbers does not have matching bit values among bits from $1$-st to $31$-st bit (i.e., considering the $31$ least significant bits of the binary representation).

For an integer $k$, let $k_2(i)$ denote the $i$-th bit in its binary representation (from right to left, indexing from 1). For example, if $k=43$, since $43=101011_2$, then $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$.

Formally, for any two numbers $x$ and $y$ in the same group, the condition $x_2(i) \neq y_2(i)$ must hold for all $1 \leq i < 32$.

What is the minimum number of groups Vlad needs to achieve his goal? Each number must fall into exactly one group.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the total number of integers.

The second line of each test case contains $n$ given integers $a_1, \ldots, a_n$ ($0 \leq a_j < 2^{31}$).

The sum of $n$ over all test cases in a test does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer  — the minimum number of groups required to satisfy the condition.

ExampleInput

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

Output

4
1
3
2
2
3
2
2
4

Note

In the first test case, any two numbers have the same last $31$ bits, so we need to place each number in its own group.

In the second test case, $a_1=0000000000000000000000000000000_2$, $a_2=1111111111111111111111111111111_2$ so they can be placed in the same group because $a_1(i) \ne a_2(i)$ for each $i$ between $1$ and $31$, inclusive.

题目大意：
Vlad有n个非负整数，他想将这些数分成若干组，使得在同一组中的任意两个数的二进制表示在第1位到第31位上都不相同。对于整数k，k_2(i)表示其二进制表示中的第i位（从右到左，从1开始索引）。例如，如果k=43，因为43=101011_2，那么43_2(1)=1，43_2(2)=1，43_2(3)=0，等等。正式地说，对于同一组中的任意两个数x和y，必须对所有1≤i<32满足x_2(i)≠y_2(i)。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——整数的总数。
- 每个测试用例的第二行包含n个给定的整数a_1,…,a_n（0≤a_j<2^31）。
- 所有测试用例中n的总和不超过2×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
```题目大意： Vlad有n个非负整数，他想将这些数分成若干组，使得在同一组中的任意两个数的二进制表示在第1位到第31位上都不相同。对于整数k，k_2(i)表示其二进制表示中的第i位（从右到左，从1开始索引）。例如，如果k=43，因为43=101011_2，那么43_2(1)=1，43_2(2)=1，43_2(3)=0，等等。正式地说，对于同一组中的任意两个数x和y，必须对所有1≤i<32满足x_2(i)≠y_2(i)。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——整数的总数。 - 每个测试用例的第二行包含n个给定的整数a_1,…,a_n（0≤a_j<2^31）。 - 所有测试用例中n的总和不超过2×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 ```