Meaningless Operations

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) of integers $a \oplus 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 \oplus b, a \> \& \> b)}.$$

Here $\oplus$ denotes the bitwise XOR operation, and $\&$ denotes the bitwise AND operation.

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, \ldots, 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 \le q \le 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, \ldots, a_q$ ($2 \le a_i \le 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.Exampleinput

3
2
3
5

output

3
1
7

Note

For the first integer the optimal choice is $b = 1$, then $a \oplus 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 \oplus 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 \oplus b = 7$, $a \> \& \> b = 0$, and the greatest common divisor of $7$ and $0$ is $7$.

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
vector<int> a = {1,1,5,1,21,1,85,73,341,89,1365,1,5461,4681,21845,1,87381,1,349525,299593,1398101,178481,5592405,1082401};
map<int, int> mp;
int ptr = 0;
for (int i = 3; i <= (1 << 25) - 1; i = i * 2 + 1) {
/*    int mx = 0;
    for (int j = 1; j < i; j++) {
      mx = max(mx, __gcd(i & j, i ^ j));
    }
    cerr << mx << ",";*/
    mp[i] = a[ptr++];
  }
  int tt;
  cin >> tt;
while (tt--) {
int n;
cin >> n;
if (mp.count(n)) {
cout << mp[n] << '\n';
    } else {
      int x = 1;
      while (x < n) {
        x = x * 2 + 1;
      }
      cout << x << '\n';
    }
  }
  return 0;
}