Can the greatest common divisor and bitwise operations have anything in common? It is time to answer this question.

Suppose you are given a positive integer a. You want to choose some integer b from 1 to a - 1 inclusive in such a way that the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers a ⊕ b and a \> \& \> b is as large as possible. In other words, you'd like to compute the following function:

$$$f(a) = max_{0 < b < a}{gcd(a ⊕ b, a \> \& \> b)}.$$$

Here ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR), and \& denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

The greatest common divisor of two integers x and y is the largest integer g such that both x and y are divided by g without remainder.

You are given q integers a_1, a_2, …, a_q. For each of these integers compute the largest possible value of the greatest common divisor (when b is chosen optimally). 

Input

The first line contains an integer q (1 ≤ q ≤ 10^3) — the number of integers you need to compute the answer for.

After that q integers are given, one per line: a_1, a_2, …, a_q (2 ≤ a_i ≤ 2^{25} - 1) — the integers you need to compute the answer for. 

Output

For each integer, print the answer in the same order as the integers are given in input.

Example

Input


3
2
3
5


Output


3
1
7

Note

For the first integer the optimal choice is b = 1, then a ⊕ b = 3, a \> \& \> b = 0, and the greatest common divisor of 3 and 0 is 3.

For the second integer one optimal choice is b = 2, then a ⊕ b = 1, a \> \& \> b = 2, and the greatest common divisor of 1 and 2 is 1.

For the third integer the optimal choice is b = 2, then a ⊕ b = 7, a \> \& \> b = 0, and the greatest common divisor of 7 and 0 is 7.
#include <bits/stdc++.h>
using namespace std;
constexpr unsigned int NKNOWN = 25;
constexpr unsigned int KNOWN[NKNOWN][2] = {
    {33554431, 1082401},
    {16777215, 5592405},
    {8388607, 178481},
    {4194303, 1398101},
    {2097151, 299593},
    {1048575, 349525},
    {524287, 1},
    {262143, 87381},
    {131071, 1},
    {65535, 21845},
    {32767, 4681},
    {16383, 5461},
    {8191, 1},
    {4095, 1365},
    {2047, 89},
    {1023, 341},
    {511, 73},
    {255, 85},
    {127, 1},
    {63, 21},
    {31, 1},
    {15, 5},
    {7, 1},
    {3, 1},
    {1, 1},
};
map<unsigned int, unsigned int> KNOWN_MAP;
unsigned int gcd(unsigned int a, unsigned int b) {
  if (a < b) swap(a, b);
  if (b == 0) return a;
  return gcd(b, a % b);
}
int solve(unsigned int A) {
  auto iter = KNOWN_MAP.find(A);
  if (iter != KNOWN_MAP.end()) return iter->second;
  unsigned int best = gcd(A ^ (A - 1), A & (A - 1));
  unsigned int bestb = A - 1;
  unsigned int inv = ~A & ((1 << (32 - __builtin_clz(A))) - 1);
  if (inv > 0) {
    unsigned int g = gcd(A ^ inv, A & inv);
    if (best < g) {
      best = g;
      bestb = inv;
    }
  }
  for (unsigned int b = A - 1; b > 0; --b) {
    if (b < best) break;
    unsigned int g = gcd(A ^ b, A & b);
    if (best < g) {
      best = g;
      bestb = b;
    }
  }
  return best;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  for (unsigned int i = 0; i < NKNOWN; ++i) {
    KNOWN_MAP.insert(make_pair(KNOWN[i][0], KNOWN[i][1]));
  }
  int Q;
  cin >> Q;
  for (int q = 0; q < Q; ++q) {
    unsigned int A;
    cin >> A;
    cout << solve(A) << "\n";
    cout.flush();
  }
  return 0;
}
