CF1601A.Array Elimination

You are given array $a_1, a_2, \ldots, a_n$, consisting of non-negative integers.

Let's define operation of "elimination" with integer parameter $k$ ($1 \leq k \leq n$) as follows:

• Choose $k$ distinct array indices $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \le n$.
• Calculate $x = a_{i_1} ~ \& ~ a_{i_2} ~ \& ~ \ldots ~ \& ~ a_{i_k}$, where $\&$ denotes the bitwise AND operation (notes section contains formal definition).
• Subtract $x$ from each of $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$; all other elements remain untouched.

Find all possible values of $k$, such that it's possible to make all elements of array $a$ equal to $0$ using a finite number of elimination operations with parameter $k$. It can be proven that exists at least one possible $k$ for any array $a$.

Note that you firstly choose $k$ and only after that perform elimination operations with value $k$ you've chosen initially.

给你一个由非负整数构成的数组 $a_1, a_2, \ldots, a_n$。

我们定义参数为 $k$（其中 $1 \leq k \leq n$）的“消去”操作如下：

• 选择 $k$ 个互不相同的数组下标 $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \le n$；
• 计算 $x = a_{i_1} ~ \& ~ a_{i_2} ~ \& ~ \ldots ~ \& ~ a_{i_k}$，其中 $\&$ 表示按位与运算（注释部分包含其形式化定义）；
• 将 $x$ 从每个 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 中减去；其余元素保持不变。

请找出所有可能的 $k$ 值，使得可以通过有限次参数为 $k$ 的消去操作，将数组 $a$ 的所有元素变为 $0$。可以证明：对任意数组 $a$，至少存在一个可行的 $k$。

注意：你需首先选定 $k$，之后的所有消去操作均必须使用该初始选定的 $k$ 值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 200\,000$) — the length of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt 2^{30}$) — array $a$ itself.

It's guaranteed that the sum of $n$ over all test cases doesn't exceed $200\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \lt 2^{30}$）—— 数组 $a$ 本身。

保证所有测试用例的 $n$ 之和不超过 $200\,000$。

For each test case, print all values $k$, such that it's possible to make all elements of $a$ equal to $0$ in a finite number of elimination operations with the given parameter $k$.

Print them in increasing order.

对于每个测试用例，输出所有满足条件的值 $k$，使得在给定参数 $k$ 下，可以通过有限次消除操作将数组 $a$ 的所有元素变为 $0$。

按升序输出这些值。

In the first test case:

• If $k = 1$, we can make four elimination operations with sets of indices ${1}$, ${2}$, ${3}$, ${4}$. Since $\&$ of one element is equal to the element itself, then for each operation $x = a_i$, so $a_i - x = a_i - a_i = 0$.
• If $k = 2$, we can make two elimination operations with, for example, sets of indices ${1, 3}$ and ${2, 4}$: $x = a_1 ~ \& ~ a_3$ $=$ $a_2 ~ \& ~ a_4$ $=$ $4 ~ \& ~ 4 = 4$. For both operations $x = 4$, so after the first operation $a_1 - x = 0$ and $a_3 - x = 0$, and after the second operation — $a_2 - x = 0$ and $a_4 - x = 0$.
• If $k = 3$, it's impossible to make all $a_i$ equal to $0$. After performing the first operation, we'll get three elements equal to $0$ and one equal to $4$. After that, all elimination operations won't change anything, since at least one chosen element will always be equal to $0$.
• If $k = 4$, we can make one operation with set ${1, 2, 3, 4}$, because $x = a_1 ~ \& ~ a_2 ~ \& ~ a_3 ~ \& ~ a_4$ $= 4$.

In the second test case, if $k = 2$ then we can make the following elimination operations:

• Operation with indices ${1, 3}$: $x = a_1 ~ \& ~ a_3$ $=$ $13 ~ \& ~ 25 = 9$. $a_1 - x = 13 - 9 = 4$ and $a_3 - x = 25 - 9 = 16$. Array $a$ will become equal to $[4, 7, 16, 19]$.
• Operation with indices ${3, 4}$: $x = a_3 ~ \& ~ a_4$ $=$ $16 ~ \& ~ 19 = 16$. $a_3 - x = 16 - 16 = 0$ and $a_4 - x = 19 - 16 = 3$. Array $a$ will become equal to $[4, 7, 0, 3]$.
• Operation with indices ${2, 4}$: $x = a_2 ~ \& ~ a_4$ $=$ $7 ~ \& ~ 3 = 3$. $a_2 - x = 7 - 3 = 4$ and $a_4 - x = 3 - 3 = 0$. Array $a$ will become equal to $[4, 4, 0, 0]$.
• Operation with indices ${1, 2}$: $x = a_1 ~ \& ~ a_2$ $=$ $4 ~ \& ~ 4 = 4$. $a_1 - x = 4 - 4 = 0$ and $a_2 - x = 4 - 4 = 0$. Array $a$ will become equal to $[0, 0, 0, 0]$.

Formal definition of bitwise AND:

Let's define bitwise AND ($\&$) as follows. Suppose we have two non-negative integers $x$ and $y$, let's look at their binary representations (possibly, with leading zeroes): $x_k \dots x_2 x_1 x_0$ and $y_k \dots y_2 y_1 y_0$. Here, $x_i$ is the $i$-th bit of number $x$, and $y_i$ is the $i$-th bit of number $y$. Let $r = x ~ \& ~ y$ is a result of operation $\&$ on number $x$ and $y$. Then binary representation of $r$ will be $r_k \dots r_2 r_1 r_0$, where:

$$r\_i = \\begin{cases} 1, ~ \\text{if} ~ x\_i = 1 ~ \\text{and} ~ y\_i = 1 \\\\ 0, ~ \\text{if} ~ x\_i = 0 ~ \\text{or} ~ y\_i = 0 \\end{cases}$$

在第一个测试用例中：

• 若 $k = 1$，我们可以执行四次消去操作，每次操作的下标集合分别为 $\{1\}$、$\{2\}$、$\{3\}$、$\{4\}$。由于单个元素的按位与（$\&$）结果即为该元素自身，因此每次操作中 $x = a_i$，从而有 $a_i - x = a_i - a_i = 0$。
• 若 $k = 2$，我们可以执行两次消去操作，例如下标集合分别为 $\{1, 3\}$ 和 $\{2, 4\}$：$x = a_1 ~ \& ~ a_3 = a_2 ~ \& ~ a_4 = 4 ~ \& ~ 4 = 4$。两次操作中均有 $x = 4$，因此第一次操作后 $a_1 - x = 0$ 且 $a_3 - x = 0$，第二次操作后 $a_2 - x = 0$ 且 $a_4 - x = 0$。
• 若 $k = 3$，则无法使所有 $a_i$ 均变为 $0$。执行第一次操作后，将得到三个值为 $0$ 的元素和一个值为 $4$ 的元素；此后所有消去操作均不再改变数组，因为每次所选元素中至少有一个恒为 $0$。
• 若 $k = 4$，我们可以执行一次消去操作，其下标集合为 $\{1, 2, 3, 4\}$，因为 $x = a_1 ~ \& ~ a_2 ~ \& ~ a_3 ~ \& ~ a_4 = 4$。

在第二个测试用例中，若 $k = 2$，则可执行如下消去操作：

• 下标集合为 $\{1, 3\}$ 的操作：$x = a_1 ~ \& ~ a_3 = 13 ~ \& ~ 25 = 9$；$a_1 - x = 13 - 9 = 4$，$a_3 - x = 25 - 9 = 16$；数组 $a$ 变为 $[4, 7, 16, 19]$。
• 下标集合为 $\{3, 4\}$ 的操作：$x = a_3 ~ \& ~ a_4 = 16 ~ \& ~ 19 = 16$；$a_3 - x = 16 - 16 = 0$，$a_4 - x = 19 - 16 = 3$；数组 $a$ 变为 $[4, 7, 0, 3]$。
• 下标集合为 $\{2, 4\}$ 的操作：$x = a_2 ~ \& ~ a_4 = 7 ~ \& ~ 3 = 3$；$a_2 - x = 7 - 3 = 4$，$a_4 - x = 3 - 3 = 0$；数组 $a$ 变为 $[4, 4, 0, 0]$。
• 下标集合为 $\{1, 2\}$ 的操作：$x = a_1 ~ \& ~ a_2 = 4 ~ \& ~ 4 = 4$；$a_1 - x = 4 - 4 = 0$，$a_2 - x = 4 - 4 = 0$；数组 $a$ 变为 $[0, 0, 0, 0]$。

按位与（bitwise AND）的严格定义如下：

我们定义按位与运算（$\&$）如下：设 $x$ 和 $y$ 为两个非负整数，考察其二进制表示（必要时可在高位补零）：$x_k \dots x_2 x_1 x_0$ 和 $y_k \dots y_2 y_1 y_0$。其中 $x_i$ 表示 $x$ 的第 $i$ 位，$y_i$ 表示 $y$ 的第 $i$ 位。令 $r = x ~ \& ~ y$ 为 $x$ 与 $y$ 进行 $\&$ 运算的结果，则 $r$ 的二进制表示为 $r_k \dots r_2 r_1 r_0$，其中：

$$r\_i = \\begin{cases} 1, ~ \\text{若} ~ x\_i = 1 ~ \\text{且} ~ y\_i = 1 \\\\ 0, ~ \\text{若} ~ x\_i = 0 ~ \\text{或} ~ y\_i = 0 \\end{cases}$$