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.
_except = {
    1: 0,
    2: 1,
    3: 1,
    4: 5,
    5: 1,
    6: 21,
    7: 1,
    8: 85,
    9: 73,
    10: 341,
    11: 89,
    12: 1365,
    13: 1,
    14: 5461,
    15: 4681,
    16: 21845,
    17: 1,
    18: 87381,
    19: 1,
    20: 349525,
    21: 299593,
    22: 1398101,
    23: 178481,
    24: 5592405,
    25: 1082401
}
regular = {
    1: 1,
    2: 3,
    3: 7,
    4: 15,
    5: 31,
    6: 63,
    7: 127,
    8: 255,
    9: 511,
    10: 1023,
    11: 2047,
    12: 4095,
    13: 8191,
    14: 16383,
    15: 32767,
    16: 65535,
    17: 131071,
    18: 262143,
    19: 524287,
    20: 1048575,
    21: 2097151,
    22: 4194303,
    23: 8388607,
    24: 16777215,
    25: 33554431
}

def e(n):
    temp = 0
    magic = True
    while n >= 1:
        if n%2 == 0:
            magic = False
        temp = temp + 1
        n = n//2
    return magic, temp

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def temp_test(n):
    _max = 0
    token = 0
    for i in range(1,n//2+1):
        _ = gcd(n-i,i)
        if _ > _max:
            _max = _
            token = i
    token_info = e(token)
    return _max, token, token_info

q = input()
q = int(q)
round = 0
while round < q:
    a = input()
    a = int(a)
    magic, info = e(a)
    print(_except[info] if magic else regular[info])
    round = round + 1