human
PYTHON3 solution for "You are given array a_1, a_2, …, a_n, consisting of non-negative integers.

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

  * Choose k distinct array indices 1 ≤ i_1 < i_2 < … < i_k ≤ n. 
  * Calculate x = a_{i_1} ~ \& ~ a_{i_2} ~ \& ~ … ~ \& ~ a_{i_k}, where \& denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND) (notes section contains formal definition). 
  * Subtract x from each of a_{i_1}, a_{i_2}, …, 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 ≤ t ≤ 10^4). Description of the test cases follows.

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

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i < 2^{30}) — array a itself.

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

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.

Example

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...":



What is a Python code to 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?
assistant
#Here is Python code to 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.
 # DEFINING SOME GOOD STUFF
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

# threading.stack_size(10**8)
# sys.setrecursionlimit(300000)
'''
-> if you are increasing recursionlimit then remember submitting using python3 rather pypy3
-> sometimes increasing stack size don't work locally but it will work on CF
'''

mod = 10 ** 9+7
inf = 10 ** 15
decision = ['NO', 'YES']
yes = 'YES'
no = 'NO'

# ------------------------------FASTIO----------------------------
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:...