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.
from sys import stdin,stdout
from itertools import combinations
from collections import defaultdict
import math 

def listIn():
    return list((map(int,stdin.readline().strip().split())))

def stringListIn():
    return([x for x in stdin.readline().split()])
    
def intIn():
    return (int(stdin.readline()))

def stringIn():
    return (stdin.readline().strip())

def gcd(a,b): 
    if (b == 0): 
         return a 
    return gcd(b, a%b) 

def maximumXOR(n, l, r): 
    x = 0
    for i in range(int(math.log2(r)), -1, -1):  
        if (n & (1 << i)): # Set bit  
            if (x > r) or (x + (1 << i) - 1 < l): 
                x ^= (1 << i) 
        else: # Unset bit 
            if (x ^ (1 << i)) <= r: 
                x ^= (1 << i) 
    return n ^ x 
 

def smallestDivisor(n): 
    if (n % 2 == 0): 
        return 2; 
    i = 3;  
    while(i * i <= n): 
        if (n % i == 0): 
            return i; 
        i += 2; 
    return n
  
if __name__=='__main__': 
    li=[]
    for i in range(2,26):
        temp="1"*i
        temp=int(temp,2)
        li.append(temp)
    #print(li)
    q=intIn()
    while(q>0):
        q-=1
        a=intIn()
        ans={}
        if a in li:
            ele=smallestDivisor(a)
            print(a//ele)
        else:
            #bitiwise and does not affect at all
            print(maximumXOR(a,1,a-1))
            """
            for b in range(1,a):
                a1,a2=a^b,a&b
                val=(a1,a2)
                ans[val]=gcd(a1,a2)
            b=ans.values()
            print(max(b))
            """
