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 = 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 ... x_2 x_1 x_0 and y_k ... 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 ... r_2 r_1 r_0, where:

$$$ r_i = \begin{cases} 1, ~ if ~ x_i = 1 ~ and ~ y_i = 1 \\\ 0, ~ if ~ x_i = 0 ~ or ~ y_i = 0 \end{cases} $$$
#include <bits/stdc++.h>
using namespace std;
long long MOD = 1e9 + 7;
template <typename T>
istream &operator>>(istream &is, vector<T> &arr) {
  typename vector<T>::iterator a;
  for (a = arr.begin(); a != arr.end(); a++) {
    is >> *a;
  }
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &arr) {
  typename vector<T>::iterator a;
  for (a = arr.begin(); a != arr.end(); a++) {
    os << *a << " ";
  }
  return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &p) {
  os << p.first << " " << p.second << '\n';
  return os;
}
long long mul(long long a, long long b, long long md = MOD) {
  return (a % md * b % md) % md;
}
long long add(long long a, long long b, long long md = MOD) {
  long long ans = a + b;
  if (ans >= md) ans -= md;
  return ans;
}
bool valid(int i, int j, int n, int m) {
  return i >= 0 && i < n && j >= 0 && j < m;
}
vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
long long binPow(long long x, long long y) {
  long long ans = 1;
  while (y > 0) {
    if (y % 2 == 1) ans = mul(ans, x);
    x = mul(x, x);
    y /= 2;
  }
  return ans;
}
long long modInverse(long long x) { return binPow(x, MOD - 2); }
struct FenwickTree {
  vector<long long> a, b;
  FenwickTree(vector<long long> a) {
    this->a = vector<long long>(1 + ((int)a.size()));
    this->b = vector<long long>(1 + ((int)a.size()));
    for (int i = int(1); i < int(1 + ((int)a.size())); i++) update(i, a[i - 1]);
  }
  int LSBit(int x) { return x & (-x); }
  void update(int x, long long val) {
    long long diff = val - a[x];
    a[x] = val;
    for (int i = x; i < ((int)b.size()); i += LSBit(i)) {
      b[i] += diff;
    }
  }
  long long sum(int x) {
    long long ans = 0;
    for (int i = x; i > 0; i -= LSBit(i)) ans += b[i];
    return ans;
  }
  long long rmq(int l, int r) { return sum(r) - sum(l - 1); }
};
vector<vector<int>> G;
void E(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  vector<int> cnt(30);
  for (int i = 0; i < int(n); i++) {
    for (int b = 0; b < int(30); b++) {
      if ((1 << b) & a[i]) cnt[b]++;
    }
  }
  for (int k = int(1); k < int(n + 1); k++) {
    bool oj = true;
    for (int b = 0; b < int(30); b++) {
      if (cnt[b] > 0 && cnt[b] % k) oj = false;
    }
    if (oj) cout << k << " ";
  }
  cout << "\n";
}
int main() {
  (ios_base::sync_with_stdio(false), cin.tie(0));
  solve();
}
