human
Write me a Python program 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 given the following:
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...":
assistant
#Here is Python program 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.
 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()