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 < i_2 < \ldots < 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.


-----Input-----

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 200000$) — 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 < 2^{30}$) — array $a$ itself.

It's guaranteed that the sum of $n$ over all test cases doesn't exceed $200000$.


-----Output-----

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.


-----Examples-----

Input
5
4
4 4 4 4
4
13 7 25 19
6
3 5 3 1 7 1
1
1
5
0 0 0 0 0
Output
1 2 4
1 2
1
1
1 2 3 4 5


-----Note-----

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} $$

Source: codeforces | Difficulty: EASY
Tags: Number theory

Bit manipulation

Mathematics

Greedy algorithms


Solutions:
import math

def array_elimination(n, a):
	counts = {i: 0 for i in range(32)}
	for ai in a:
		bin_ai = '{:032b}'.format(ai)
		for i in range(32):
			if bin_ai[i] == '1':
				counts[i] += 1
	groups = []
	for i in range(32):
		if counts[i] > 0:
			groups += [counts[i]]
	if len(groups) == 0:
		print(' '.join(map(str, range(1, n + 1))))
		return
	counts_by_divisor = {}
	for group_size in groups:
		for divisor in get_divisors(group_size):
			if divisor in counts_by_divisor:
				counts_by_divisor[divisor] += 1
			else:
				counts_by_divisor[divisor] = 1
	k = []
	for divisor in counts_by_divisor:
		if counts_by_divisor[divisor] == len(groups):
			k += [divisor]
	print(' '.join(map(str, sorted(k))))

def get_divisors(value):
	m = int(math.ceil(math.sqrt(value)))
	for d in range(1, m + 1):
		if value % d == 0:
			e = value // d
			if d < e:
				yield d
				yield e
			elif d == e:
				yield d
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	array_elimination(n, a)


from math import gcd

def b(n, g):
	s = bin(n).replace('0b', '')
	while len(s) < g:
		s = '0' + s
	return s

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		jjk = 0
		if max(a) == min(a) and min(a) == 0:
			for i in range(n):
				print(i + 1, end=' ')
			print()
			continue
		for i in range(n):
			jjk = max(len(bin(a[i])) - 2, jjk)
		j = []
		for i in range(n):
			j += [b(a[i], jjk)]
		k = {}
		for i in range(n):
			for jk in range(jjk):
				if j[i][jk] == '1':
					if jk in k:
						k[jk] += 1
					else:
						k[jk] = 1
		jh = 0
		for i in k:
			jh = gcd(jh, k[i])
		l = []
		for i in range(1, jh + 1):
			if jh % i == 0:
				print(i, end=' ')
		print()
main()


import sys
input = sys.stdin.readline

def extend_euc(a, b):
	if b == 0:
		return (a, 1, 0)
	(gcd, x, y) = extend_euc(b, a % b)
	return (gcd, y, x - a // b * y)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	bits = [0] * len(list(format(sum(a), 'b')))
	for e in a:
		t = list(format(e, 'b'))
		bl = t[::-1]
		for i in range(len(bl)):
			if bl[i] == '1':
				bits[i] += 1
	gcd = min(bits)
	for e in bits:
		if e:
			gcd = extend_euc(gcd, e)[0]
	if gcd == 0:
		for i in range(1, n + 1):
			print(i, end=' ')
	else:
		for i in range(1, gcd + 1):
			if gcd % i == 0:
				print(i, end=' ')
	print()


import math
n = int(input())
for e in range(n):
	t = int(input())
	l = list(map(int, input().split()))
	mx = max(l)
	if mx == 0:
		ans = []
		for i in range(1, t + 1):
			ans.append(i)
		print(*ans)
	else:
		q = int(math.log(mx, 2)) + 1
		a = []
		for i in range(q):
			c = 0
			for j in l:
				if j & 1 << i != 0:
					c += 1
			a.append(c)
		ans = []
		for i in range(1, max(a) + 1):
			chk = 0
			for j in a:
				if j % i == 0:
					continue
				else:
					chk = 1
					break
			if chk == 0:
				ans.append(i)
		print(*ans)


from math import gcd
T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	val = 0
	for i in range(31):
		ct = 0
		for j in range(n):
			if 1 << i & arr[j] != 0:
				ct += 1
		val = gcd(val, ct)
	if val == 0:
		print(*range(1, n + 1))
		continue
	for i in range(1, val + 1):
		if val % i == 0:
			print(i, end=' ')
	print()


from math import gcd
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	g = 0
	for b in range(0, 30):
		c = 0
		for x in a:
			if x & 1 << b:
				c = c + 1
		g = gcd(g, c)
	for i in range(1, n + 1):
		if g % i == 0:
			print(i, end=' ')
	print()


def divisors(n):
	if n == 1:
		return [1]
	l = []
	for i in range(1, n // 2 + 1):
		if n % i == 0:
			l += [i]
	return l + [n]
d = {}
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	u = set([x.count('1') for x in zip(*(f'{x:031b}' for x in a))])
	res = []
	for el in u:
		if el == 0:
			continue
		if el in d:
			div = d[el]
		else:
			div = divisors(el)
			d[el] = div
		if res == []:
			res = div.copy()
			continue
		new = []
		for f in res:
			if f in div:
				new += [f]
		res = new.copy()
	if res == []:
		res = [i for i in range(1, n + 1)]
	print(*res, sep=' ')


import math
from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, gcd, log
import bisect
import sys
import random
import heapq

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def main():
	for _ in range(int(input())):
		n = int(input())
		a = get_array()
		cnt = [0] * 31
		for i in range(31):
			for j in range(n):
				if a[j] & 1 << i:
					cnt[i] += 1
		cum_gcd = max(cnt)
		ok = False
		for i in range(30):
			if cnt[i] > 0:
				ok = True
			if ok:
				cum_gcd = gcd(cum_gcd, cnt[i])
		if cum_gcd == 0:
			print(*list(range(1, n + 1)))
			continue
		ans = []
		for i in range(1, int(sqrt(cum_gcd)) + 1):
			if cum_gcd % i == 0:
				ans.append(i)
				if i * i != cum_gcd:
					ans.append(cum_gcd // i)
		ans.sort()
		print(*ans)
main()


import sys
import bisect
import math
input = sys.stdin.readline

def solve():
	n = int(input())
	k = lambda x: bin(int(x))[2:][::-1]
	a = list(map(k, input().split()))
	m = 0
	for i in a:
		m = max(m, len(i))
	c = [0] * m
	for i in a:
		for j in range(len(i)):
			if i[j] == '1':
				c[j] += 1
	s = set(c)
	s = list(s)
	gcd = s[0]
	for i in range(1, len(s)):
		gcd = math.gcd(gcd, s[i])
	for i in range(1, n + 1):
		if gcd % i == 0:
			print(i, end=' ')
	print()
t = int(input())
for _ in range(t):
	solve()


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	net = [0] * 31
	for i in range(31):
		for e in A:
			if e & 1 << i:
				net[i] += 1
	ans = []
	for k in range(1, n + 1):
		ok = True
		for i in range(31):
			if net[i] % k != 0:
				ok = False
				break
		if ok:
			ans.append(k)
	print(*ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


import sys
from functools import reduce
import math
input = sys.stdin.readline

def get_integers():
	return map(int, input().strip().split())
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = [int(x) for x in input().strip().split()]
	cnt = [0] * 30
	for element in arr:
		for i in range(30):
			if element & 1 << i:
				cnt[i] += 1
	if sum(cnt) == 0:
		ans = list(range(1, n + 1))
		print(*ans)
		continue
	cnt_set = set(cnt)
	gcd = reduce(math.gcd, cnt_set)
	ans = []
	for i in range(1, int(math.sqrt(gcd)) + 1):
		if gcd % i == 0:
			ans.append(i)
			if i != gcd // i:
				ans.append(gcd // i)
	print(*sorted(ans))


import sys
input = sys.stdin.buffer.readline
from math import gcd, log, ceil, sqrt
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	g = 0
	if max(a) == 0:
		for i in range(len(a)):
			print(i + 1, end=' ')
	else:
		for _ in range(1 + ceil(log(max(a), 2))):
			an = 0
			for i in range(len(a)):
				an += a[i] % 2
				a[i] = a[i] // 2
			g = gcd(g, an)
		if g == 0:
			print(1)
		for k in range(1, g + 1):
			if g % k == 0:
				print(k, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mask = 1
	bits = []
	for _ in range(30):
		cnt = 0
		for i in arr:
			if i & mask:
				cnt += 1
		bits.append(cnt)
		mask <<= 1
	ans = []
	for k in range(1, n + 1):
		f = 1
		for i in bits:
			if i % k:
				f = 0
				break
		if f:
			ans.append(k)
	print(*ans)


import math

def case():
	n = int(input())
	a = list(map(int, input().split()))
	if all((x == 0 for x in a)):
		print(' '.join(map(str, range(1, n + 1))))
		return
	counts = [0] * 30
	for x in a:
		for i in range(30):
			if 1 << i & x:
				counts[i] += 1
	factors = []
	for cnt in counts:
		if cnt == 0:
			continue
		upper = math.ceil(math.sqrt(cnt))
		f = set()
		for i in range(1, upper + 1):
			if cnt % i == 0:
				f.add(i)
				f.add(cnt // i)
		factors.append(f)
	while len(factors) > 1:
		a = factors.pop()
		factors[-1] &= a
	print(' '.join(map(str, sorted(factors[0]))))

def main():
	T = int(input())
	for _ in range(T):
		case()
main()


import sys
sys.setrecursionlimit(100000)

def _r():
	return sys.stdin.buffer.readline()

def rs():
	return _r().decode('ascii').strip()

def rn():
	return int(_r())

def rnt():
	return tuple(map(int, _r().split()))

def rnl():
	return list(rnt())
import math, functools

def solve(n, a):
	if sum(a) == 0:
		return list(range(1, n + 1))
	bts = [0] * 32
	for x in a:
		for bs in range(32):
			if x & 1 << bs > 0:
				bts[bs] += 1
	g = 0
	for x in bts:
		if x > 0:
			g = math.gcd(g, x)
	sol = []
	x = 1
	while x * x <= g:
		if g % x == 0:
			sol.append(x)
			if x != g // x:
				sol.append(g // x)
		x += 1
	return sorted(sol)
for _ in range(rn()):
	n = rn()
	a = rnl()
	print(' '.join(map(str, solve(n, a))))


import sys
import math
inp = sys.stdin.readline

def solve():
	n = int(inp())
	c = [0] * 31
	for i in map(int, inp().split()):
		j = 0
		while i > 0:
			if i & 1:
				c[j] += 1
			i //= 2
			j += 1
	d = 0
	for v in c:
		d = math.gcd(d, v)
	if d == 0:
		print(' '.join(map(str, range(1, n + 1))))
	else:
		a = []
		for i in range(1, d + 1):
			if i * i > d:
				break
			if d % i == 0:
				a.append(i)
				if i * i != d:
					a.append(d // i)
		a.sort()
		print(' '.join(map(str, a)))

def main():
	for i in range(int(inp())):
		solve()
main()


def array_eliminations(arr, n):
	bit_count = [0 for _ in range(30)]
	num = 1
	for i in range(30):
		for elm in arr:
			k = elm & num
			if k != 0:
				bit_count[i] += 1
		num *= 2
	results = []
	for k in range(1, n + 1):
		flag = True
		for i in range(30):
			if bit_count[i] % k != 0:
				flag = False
				break
		if flag:
			results.append(str(k))
	return ' '.join(results)
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().rstrip().split()))
	ans = array_eliminations(a, n)
	print(ans)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def printAllDivisors(arr):
	N = len(arr)
	g = arr[0]
	divisors = dict()
	for i in range(1, N):
		g = gcd(arr[i], g)
	for i in range(1, g + 1):
		if i * i > g:
			break
		if g % i == 0:
			divisors[i] = 1
			if g // i != i:
				divisors[g // i] = 1
	ans = ''
	for it in sorted(divisors):
		ans += str(it) + ' '
	ans.strip()
	print(ans)

def b(a):
	y = str(bin(int(a)))[2:]
	l = len(y)
	return '0' * (30 - l) + y
t = int(input())
for iasdfc in range(t):
	n = int(input())
	ar = list(map(b, input().split()))
	ar2 = []
	for ind in range(30):
		count = 0
		for bind in ar:
			if bind[ind] == '1':
				count += 1
		if count:
			ar2.append(count)
	if ar2 == []:
		print(' '.join(map(str, range(1, n + 1))))
	else:
		printAllDivisors(ar2)


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	n = int(stdin.readline())
	N = n
	a = list(map(int, stdin.readline().split()))
	lis = [0] * 31
	for i in range(N):
		for j in range(31):
			if 2 ** j & a[i] > 0:
				lis[j] += 1
	ans = []
	for i in range(1, n + 1):
		for j in range(31):
			if lis[j] % i != 0:
				break
		else:
			ans.append(i)
	ANS.append(' '.join(map(str, ans)))
print('\n'.join(ANS))


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
inf = 4294967295
md = 998244353
from math import gcd

def factors(a):
	if a <= 0:
		return [0]
	(dd0, dd1) = ([], [])
	for d in range(1, round(a ** 0.5) + 1):
		if a % d:
			continue
		dd0.append(d)
		dd1.append(a // d)
	if dd0[-1] == dd1[-1]:
		dd1.pop()
	return dd0 + dd1[::-1]

def solve():
	n = II()
	aa = LI()
	cnt = [0] * 32
	for a in aa:
		for i in range(32):
			cnt[i] += a >> i & 1
	g = 0
	for c in cnt:
		g = gcd(g, c)
	if g:
		ans = factors(g)
	else:
		ans = list(range(1, n + 1))
	print(*ans)
for testcase in range(II()):
	solve()


import heapq
import sys
from math import *
import threading
from heapq import *
from itertools import count
from pprint import pprint
from collections import defaultdict
from heapq import heapify, heappop, heappush
mod = 10 ** 9 + 7
inf = 10 ** 15
decision = ['NO', 'YES']
yes = 'YES'
no = 'NO'
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

	def npr(self, n, k):
		if k < 0 or n < k:
			return 0
		f = self.factorial
		return f.calc(n) * f.invFactorial(n - k) % self.MOD

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

def lower_bound(li, num):
	answer = len(li)
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = len(li)
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			start = middle + 1
		else:
			answer = middle
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val):
	ans = -1
	lb = 0
	ub = len(li) - 1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [li[0]]
	for i in range(1, len(li)):
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [{1, i} for i in range(n + 1)]
	p = 2
	while p <= n:
		for i in range(p * 2, n + 1, p):
			prime[i].add(p)
		p += 1
	return prime

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def prod(li):
	ans = 1
	for i in li:
		ans *= i
	return ans

def given():
	a = list(map(int, input().split()))
	return a

def givenStringList():
	s = list(input())
	return s

def givenStringListInt():
	s = [int(x) for x in givenStringList()]
	return s

def main():
	karmanya = given()[0]
	while karmanya != 0:
		karmanya -= 1
		n = given()[0]
		a = given()
		if len(set(a)) == 1 and a[0] == 0:
			print(*[i for i in range(1, n + 1)])
			continue
		bitmask = [0] * 30
		for i in a:
			x = bin(i)[2:][::-1]
			for j in range(len(x)):
				if x[j] == '1':
					bitmask = bitmask[:j] + [bitmask[j] + 1] + bitmask[j + 1:]
		ans = 0
		for i in bitmask:
			ans = gcd(ans, i)
		factors = set()
		for i in range(1, int(sqrt(ans)) + 1):
			if ans % i == 0:
				factors.add(i)
				factors.add(ans // i)
		factors = sorted(factors)
		print(*factors)
main()


import math
for _ in range(int(input().strip())):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	binarr = [None] * n
	counts = [0] * 64
	for i in range(n):
		temp = bin(arr[i])[2:]
		binarr[i] = temp[::-1]
		for j in range(len(binarr[i])):
			if binarr[i][j] == '1':
				counts[j] += 1
	g = 0
	for i in counts:
		g = math.gcd(g, i)
	for i in range(1, n + 1):
		if g % i == 0:
			print(i, end=' ')
	print()


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factors(n):
	import math
	arr = []
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			arr.append(i)
			if i != n // i:
				arr.append(n // i)
	return sorted(arr)

def fun():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		if arr == [0] * n:
			for i in range(n):
				print(i + 1, end=' ')
			print()
			continue
		size = len(bin(max(arr))[2:])
		bits = [0 for i in range(size)]
		for each in arr:
			idx = size - 1
			while each:
				if each & 1 == 1:
					bits[idx] += 1
				each = each >> 1
				idx -= 1
		hcf = None
		for i in bits:
			if i != 0:
				hcf = i
				break
		for i in bits:
			if i == 0:
				continue
			hcf = gcd(hcf, i)
		x = factors(hcf)
		for each in x:
			print(each, end=' ')
		print()
fun()


import math as m
from functools import reduce

def factors(n):
	if n == 1:
		return [1]
	if n == 2:
		return [1, 2]
	if n == 4:
		return [1, 2, 4]
	l = []
	u = []
	l.append(1)
	u.append(n)
	if n % 2 == 0:
		l.append(2)
		u.append(n // 2)
	for i in range(3, int(n ** 0.5) + 1):
		if n % i == 0:
			l.append(i)
			u.append(n // i)
	u = u[::-1]
	if l[-1] == u[0]:
		u = u[1:]
	return l + u

def isSorted(arr):
	i = arr[0]
	for j in arr[1:]:
		if i > j:
			return False
		i = j
	return True
i = input()
inp = []
for a in range(0, int(i)):
	input()
	inp.append([int(x) for x in input().split()])

def logic(arr):
	n = len(arr)
	if n == 1:
		return '1'
	freqs = [0] * 31
	for i in arr:
		b = bin(i)[2:]
		for i in range(len(b)):
			if b[-i - 1] == '1':
				freqs[i] += 1
	g = m.gcd(freqs[0], freqs[1])
	for x in freqs[2:]:
		g = m.gcd(g, x)
	if g == 0:
		return ' '.join([str(j) for j in range(1, n + 1)])
	else:
		return ' '.join([str(j) for j in factors(g)])
for arr in inp:
	print(logic(arr))


from functools import reduce
from math import gcd
input = __import__('sys').stdin.readline

def solve():
	n = int(input())
	count = [0] * 32
	for x in map(int, input().split()):
		for i in range(32):
			count[i] += x >> i & 1
	d = reduce(gcd, count)
	for i in range(1, n + 1):
		if d % i == 0:
			print(i, end=' ')
	print()
for _ in range(int(input())):
	solve()


import sys

def solve():
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	bits = [0] * 30
	for i in range(30):
		cur_long_int = 1 << i
		for num in arr:
			if num & cur_long_int != 0:
				bits[i] += 1
	print(1, end=' ')
	for k in range(1, n):
		flag = True
		for no_of_bit in bits:
			if no_of_bit % (k + 1):
				flag = False
				break
		if flag:
			sys.stdout.write(str(k + 1) + ' ')
	sys.stdout.write('\n')

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		solve()
main()


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	l = len(bin(max(a))) - 2
	c = deque([0 for x in range(l)])
	for i in a:
		b = bin(i)[2:][::-1]
		for j in range(len(b)):
			c[j] = c[j] + int(b[j])
	ans = deque([int(x) for x in range(1, n + 1)])
	for i in range(2, n + 1):
		for j in c:
			if j % i != 0:
				ans.remove(i)
				break
	for i in ans:
		print(i, end=' ')
	print()


import sys
import collections

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def solve(nums):
	d = collections.defaultdict(int)
	for i in nums:
		for j in range(32):
			if i & 1 << j:
				d[j] += 1
	cnt = []
	for i in d:
		cnt.append(d[i])
		if len(cnt) == 2:
			cnt = [find_gcd(cnt[0], cnt[1])]
	gcd = cnt[0]
	ans = set()
	t = 1
	while 1:
		if gcd % t == 0:
			ans.add(t)
			ans.add(gcd // t)
		t += 1
		if t * t > gcd:
			break
	return sorted(list(ans))
T = int(input())
for _ in range(T):
	n = int(input())
	nums = get_ints()
	if nums.count(0) == len(nums):
		print(*list(range(1, 1 + len(nums))))
	else:
		print(*solve(nums))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	cou = [0] * 30
	res = []
	for bit in range(30):
		for x in a:
			if x & 1 << bit:
				cou[bit] += 1
	for k in range(1, n + 1):
		ok = True
		for numbit in cou:
			if numbit % k != 0:
				ok = False
				break
		if ok:
			res.append(k)
	print(*res)


import sys
input = sys.stdin.readline
for _ in [0] * int(input()):
	n = int(input())
	y = [0] * 33
	for i in map(int, input().split()):
		for (j, k) in enumerate(bin(i)[::-1]):
			if k == '1':
				y[j] = y[j] + 1
	for i in range(1, n + 1):
		if all((x % i == 0 for x in y)):
			print(i, end=' ')
	print()


import math
for tc in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	bits = 30
	cnts = [0] * 30
	for b in range(bits):
		for num in a:
			if num & 1 << b > 0:
				cnts[b] += 1
	g = 0
	for c in cnts:
		g = math.gcd(g, c)
	if g == 0:
		print(*range(1, n + 1))
	else:
		ans = []
		for x in range(1, int(math.sqrt(g) + 1)):
			b = g // x
			if g % x == 0:
				ans.append(x)
				if x != b:
					ans.append(b)
		print(*sorted(ans))


from sys import stdin
from math import gcd, sqrt

def divisorGenerator(n):
	large_divisors = []
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			yield i
			if i * i != n:
				large_divisors.append(n // i)
	for divisor in reversed(large_divisors):
		yield divisor
for _ in range(int(stdin.readline())):
	count = [0] * 30
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	for i in a:
		b = bin(i)[2:][::-1]
		for j in range(len(b)):
			if b[j] == '1':
				count[29 - j] += 1
	res = max(count)
	for i in count:
		if i > 0:
			res = gcd(res, i)
		if res == 1:
			break
	if res == 0:
		print(*list(range(1, n + 1)))
	else:
		print(*list(divisorGenerator(res)))


def gcd(a, b):
	if b > a:
		(a, b) = (b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	cnt = [0 for i in range(30)]
	for i in a:
		for j in range(31):
			if i & 1 << j:
				cnt[j] += 1
	ans = 0
	for i in cnt:
		ans = gcd(ans, i)
	i = 1
	if ans == 0:
		for i in range(i, n + 1):
			print(i, end=' ')
		print()
		continue
	for i in range(1, ans + 1):
		if ans % i == 0:
			print(i, end=' ')
	print()


import sys
input = lambda : sys.stdin.readline().rstrip()
write = lambda x: sys.stdout.write(x + '\n')
debug = lambda x: sys.stderr.write(x + '\n')
writef = lambda x: print('{:.12f}'.format(x))

def fs(n):
	s = set()
	for i in range(1, int(n ** 0.5) + 2):
		if n % i == 0:
			s.add(i)
			s.add(n // i)
	l = sorted(list(s))
	return l
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = max(a).bit_length()
	from math import gcd
	vs = [0] * b
	for v in a:
		for i in range(b):
			if v >> i & 1:
				vs[i] += 1
	g = 0
	for val in vs:
		g = gcd(g, val)
	if g == 0:
		res = list(range(1, n + 1))
	else:
		res = fs(g)
	write(' '.join(map(str, res)))


from math import *
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(_) for _ in input().split()]
	if max(nums) == 0:
		print(' '.join([str(i) for i in range(1, n + 1)]))
		continue
	cnts = [0] * 30
	for x in nums:
		for i in range(30):
			if x & 1 << i:
				cnts[i] += 1
	cnts = [c for c in cnts if c > 0]
	m = cnts[0]
	for c in cnts:
		m = gcd(m, c)
	ans = [1]
	if m > 1:
		ans.append(m)
		for i in range(2, min(int(sqrt(m)) + 1, m)):
			if m % i == 0:
				ans.append(i)
				ans.append(m // i)
	ans = sorted(set(ans))
	print(' '.join([str(i) for i in ans]))