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.


-----Example-----
Input
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$.

Difficulty: interview

Starter code:

Solutions:
q = int(input())

def racunaj():
	s = []
	for i in range(27):
		d = 2
		n = 2**i - 1
		z = 1
		while d*d <= n:
			if n % d == 0:
				z = n // d
				break
			d += 1
		s.append(z)
	return s

najdel = racunaj()
# print(najdel)

for _q in range(q):
	n = int(input())
	z = 1
	c = 1
	while z < n:
		z = 2*z+1
		c += 1
	if z > n:
		print(z)
	else:
		print(najdel[c])

import math
q=int(input())
for u in range(q):
    a=int(input())
    if math.log2(a+1)==int(math.log2(a+1)):
        q=1
        found=False
        while q<a**0.5:
            q+=1
            if a%q==0:
                found=True
                break
        if found:
            print(a//q)
        else:
            print(1)
    else:
        print(2**math.ceil(math.log2(a+1))-1)

from sys import setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

def largest_factor(x):
  ans = 1
  for y in range(2, 2**13):
    if x % y == 0:
      ans = max(ans, x // y)
  return ans

def solve(a):
  highest_bit = max(1 << i for i in range(30) if ((1 << i) & a) > 0)
  M = highest_bit * 2 - 1
  return M if a != M else largest_factor(M)

q = read()
for _ in range(q):
  a = read()
  print(solve(a))

for i in range(int(input())):
    n = int(input())
    lol = str(bin(n))[2:]
    if '0' in lol:
        print(2 ** (len(lol)) - 1)
    else:
        fl = 0
        hom = (2 ** len(lol)) - 1
        for z in range(3, int(hom**0.5) + 1):
            if hom % z == 0:
                print(hom // z)
                fl = 1
                break
        if not fl:
            print(1)

ii = lambda: int(input())
mi = lambda: list(map(int, input().split()))
li = lambda: list(mi())

d = {
    1: 0,
    3: 1,
    7: 1,
    15: 5,
    31: 1,
    63: 21,
    127: 1,
    255: 85,
    511: 73,
    1023: 341,
    2047: 89,
    4095: 1365,
    8191: 1,
    16383: 5461,
    32767: 4681,
    65535: 21845,
    131071: 1,
    262143: 87381,
    524287: 1,
    1048575: 349525,
    2097151: 299593,
    4194303: 1398101,
    8388607: 178481,
    16777215: 5592405,
    33554431: 1082401,
}

for _ in range(ii()):
    n = ii()
    if n in d:
        ans = d[n]
    else:
        ans = 2 ** (n.bit_length()) - 1
    print(ans)


from math import sqrt
q = int(input())
for _ in range(q):
	a = int(input())
	bi = format(a, 'b')
	if bi.count("0") == 0:
		for i in range(2, int(sqrt(a))+1):
			if a%i == 0:
				print(a//i)
				break
		else:
			print(1)
	else:
		print(pow(2, len(bi)) - 1)

ans = {3: 1, 7: 1, 15: 5, 31: 1, 63: 21, 127: 1, 255: 85, 511: 73, 1023: 341, 2047: 89, 4095: 1365, 8191: 1, 16383: 5461, 32767: 4681, 65535: 21845, 131071: 1, 262143: 87381, 524287: 1, 1048575: 349525, 2097151: 299593, 4194303: 1398101, 8388607: 178481, 16777215: 5592405, 33554431: 1082401}

for i in range(int(input())):
    n = int(input())
    if n in ans:
        print(ans[n])
    else:
        x = 3
        while x <= n:
            x = 2*x+1
        print(x)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

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

def stupid(x):
	r = 1
	for i in range(1, x):
		r = max(r, gcd(i&x, i^x))
	return r

d = dict()
d[511] = 73
d[2047] = 89
d[32767] = 4681
d[2097151] = 299593
d[8388607] = 178481
d[33554431] = 1082401
def smart(x):
	if x in d:
		return d[x]
	if (x & (x+1)) == 0:
		i = 0
		while ((1<<i)-1) != x:
			i += 1
		if i % 2 == 0:
			z = 0
			for i in range(0,i,2):
				z += (1<<i)
			return z
		else:
			return 1
	else:
		i = 1
		z = 0
		while i < x:
			if (i & x) == 0:
				z += i
			i *= 2
		return x+z

q = mint()
for i in range(q):
	x = mint()
	print(smart(x))
	#if (x & (x+1)) == 0:
	#	a = stupid(x)
	#	b = smart(x)
	#	if a != b:
	#		print(x,a,b)


import sys
input=sys.stdin.readline

q=int(input())
x=[]
for i in range(q):
    v=int(input())
    tv=v
    cnt,len=0,0
    while tv>0:
        if tv&1: cnt+=1
        len+=1
        tv//=2
    if cnt!=len:
        print(2**len-1)
    else:
        a=1
        i=2
        while i*i<=v:
            if v%i==0:
                a=v//i
                break
            i+=1
        print(a)

import math
q = int(input())

for _ in range(q):
    n = int(input())
    i = 0
    while 2**i <= n:
        i += 1
    if n == 2**i-1:
        for j in range(2,max(2,int(math.sqrt(n))+1)):
            if n%j == 0:
                print(n//j)
                break
        else:
            print(1)
    else:
        print(2**i-1)


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

def f(a):
    best = -1
    tag = None

    for b in range(1,a):
        d = gcd(a^b, a&b)
        if d > best:
            best = d
            tag = b
    return best, tag

def f2(a):
    for b in range(a-1,0,-1):
        if a % b == 0:
            return b

special = dict()

# for i in range(2, 26):
#     num = 2**i - 1
#     best = f2(num)
#     special[num] = best

# print(special)
special = {3: 1, 7: 1, 15: 5, 31: 1, 63: 21, 127: 1, 255: 85, 511: 73, 1023: 341, 2047: 89, 4095: 1365, 8191: 1, 16383: 5461, 32767: 4681, 65535: 21845, 131071: 1, 262143: 87381, 524287: 1, 1048575: 349525, 2097151: 299593, 4194303: 1398101, 8388607: 178481, 16777215: 5592405, 33554431: 1082401}
    
q = int(input())

for test in range(q):
    a = int(input())
    if a in special:
        print(special[a])
    else:
        length = len(bin(a)) - 2
        print(2**length - 1)



import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
b = [2**i for i in range(30)]
c  = []
ans=[1,
 1,
 1,
 1,
 5,
 1,
 21,
 1,
 85,
 73,
 341,
 89,
 1365,
 1,
 5461,
 4681,
 21845,
 1,
 87381,
 1,
 349525,
 299593,
 1398101,
 178481,
 5592405,
 1082401,
 22369621,
 19173961,
 89478485,
 2304167]
for i in range(30):
        c.append(b[i]-1)
for i in range(n):
        if a[i] in c:
                print(ans[c.index(a[i])])
        else:
                j = 0
                while b[j] <= a[i]:
                        j+=1
                print(c[j])

l = {}
ll = {3: 1, 7: 1, 15: 5, 31: 1, 63: 21, 127: 1, 255: 85, 511: 73, 1023: 341, 2047: 89, 4095: 1365, 8191: 1, 16383: 5461, 32767: 4681, 65535: 21845, 131071: 1, 262143: 87381, 524287: 1, 1048575: 349525, 2097151: 299593, 4194303: 1398101, 8388607: 178481, 16777215: 5592405, 33554431: 1082401}
def gcd(a,b):
    if b == 0 :
        return a 
    else:
        return gcd(b,b%a)
q = int(input())
for i in range(q):
    x = int(input())
    if x in ll.keys():
        print(ll[x])
        continue
    y = 0 
    for j in range(30):
        xx = 2**j 
        if xx & x :
            y = j
    y += 1
    ans = 2**y - 1
    print(ans)

dic={3:1,7:1,15:5,31:1,63:21,127:1,255:85,511:73,1023:341,2047:89,4095:1365,8191:1,16383:5461,32767:4681,65535:21845,131071:1,262143:87381,524287:1,1048575:349525,2097151:299593,4194303:1398101,8388607:178481,16777215:5592405,33554431:1082401}
l=[3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863]
def f(i):
    for j in l:
        if j==i:
            return dic[j]
        elif j>i:
            return j
n=int(input())
for query in range(n):
    print(f(int(input())))

# -*- coding: utf-8 -*-
# @Time    : 2019/2/7 22:08
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Meaningless Operations.py

import math

def main():
    num_dict = {
        2: 3,
        3: 1,
        7: 1,
        15: 5,
        31: 1,
        63: 21,
        127: 1,
        255: 85,
        511: 73,
        1023: 341,
        2047: 89,
        4095: 1365,
        8191: 1,
        16383: 5461,
        32767: 4681,
        65535: 21845,
        131071: 1,
        262143: 87381,
        524287: 1,
        1048575: 349525,
        2097151: 299593,
        4194303: 1398101,
        8388607: 178481,
        16777215: 5592405,
        33554431: 1082401,
    }

    q = int(input())
    for _ in range(q):
        a = int(input())
        if a in num_dict:
            print(num_dict[a])
        else:
            temp = int(math.log(a, 2))
            print(pow(2, temp + 1) - 1)

    # for i in range(2, 500):
    #     f = 0
    #     for j in range(1, i):
    #         f = max(f, math.gcd(i ^ j, i & j))
    #     print(i, 'F(A)', f)
    #
    # for k in range(1, 26):
    #     i = pow(2, k) - 1
    #     f = 0
    #     for j in range(1, i):
    #         f = max(f, math.gcd(i ^ j, i & j))
    #     print(i, ':', f, ',')


def __starting_point():
    main()

__starting_point()

Q=int(input())
A=[int(input()) for i in range(Q)]

OTHER={2**i-1 for i in range(2,26)}
OT=[2**i-1 for i in range(1,26)]
ANSDICT={3: 1, 7: 1, 15: 5, 31: 1, 63: 21, 127: 1, 255: 85, 511: 73, 1023: 341, 2047: 89, 4095: 1365, 8191: 1, 16383: 5461, 32767: 4681, 65535: 21845, 131071: 1, 262143: 87381, 524287: 1, 1048575: 349525, 2097151: 299593, 4194303: 1398101, 8388607: 178481, 16777215: 5592405, 33554431: 1082401}

for a in A:
    if a in OTHER:
        print(ANSDICT[a])
    else:
        for i in range(30):
            if a<OT[i]:
                print(OT[i])
                break


        


import math

def find_largest_non_trivial_divisor(n):
    bound = min(math.ceil(math.sqrt(n) + 2) + 1, n)
    for d in range(2, bound):
        if n % d == 0:
            return d
    return n

num_tests = int(input())
for _ in range(num_tests):
    n = int(input())



    larg_bit_pos = 0
    x = n
    while x > 1:
        x //= 2
        larg_bit_pos += 1

    best0 = 2**(larg_bit_pos+1) - 1
    if n != best0:
        print(best0)
    else:
        d = find_largest_non_trivial_divisor(n)
        print(n // d)



import math

def solve(n):
    if n == 2:
        return 3
    bad = [1, 1, 5, 1, 21, 1, 85, 73, 341, 89, 1365, 1, 5461, 4681, 21845, 1, 87381, 1, 349525, 299593, 1398101, 178481, 5592405, 1082401]
    if 2 ** math.floor(math.log2(n)) <= n <= 2 ** (math.floor(math.log2(n)) + 1) - 2:
        return (2 ** math.ceil(math.log2(n)) - 1)
    else:
        return bad[math.floor(math.log2(n)) - 1]
        
q = int(input())
for i in range(q):
    print(solve(int(input())))

q = int(input())
A = [1] * 26
for i in range(1, 26):
	for j in range(2, int((2 ** i - 1) ** 0.5) + 1):
		if (2 ** i - 1) % j == 0:
			A[i] = (2 ** i - 1) // j
			break
for i in range(q):
	n = int(input())
	s = bin(n)[2:]
	if s != '1' * len(s):
		print(2 ** len(s) - 1)
	else:
		print(A[len(s)])

3

q = int(input())
for i in range(q):
    a = int(input())
    ans = 1
    while ans <= a:
        ans *= 2
    if a < ans - 1:
        print(ans - 1)
    else:
        ans = 1
        d = 2
        while d * d <= a:
            if a % d == 0:
                ans = a // d
                break
            d += 1
        print(ans)


def find_log(number):
    counter = 1
    while number > 1:
        number = number // 2
        counter += 1
    return counter

def __starting_point():    
    
    q = int(input())
    a = [0 for i in range(q)]
    for i in range(q):
        a[i] = int(input())
    
    NUMS = [0 for i in range(24)]
    for i in range(24):
        NUMS[i] = 2**(i+2)-1
    PRIMES = [3, 7, 3, 31, 3, 127, 3, 7, 3, 23, 3, 8191, 3, 7, 3, 131071, 3, 524287, 3, 7, 3, 47, 3, 31]
    
    for i in range(q):
        if a[i] not in NUMS:
            k = find_log(a[i])
            print(2**k-1)
        else:
            index = -1
            found = False
            while not found:
                index += 1
                if NUMS[index] == a[i]:
                    found = True
            print(int(a[i]/PRIMES[index]))
__starting_point()

def intlog2(n):
    if n <= 0:
        return -1
    i = 0
    while 2**i <= n:
        i += 1
    return i-1

def isfull(n):
    a = intlog2(n)
    if n == (1<<a+1) - 1:
        return 1
    else:
        return 0

def calc(n):
    a  = intlog2(n)
    if isfull(n):
        return [1, 1, 5, 1, 21, 1, 85, 73, 341, 89, 1365, 1, 5461, 4681, 21845, 1, 87381, 1, 349525, 299593, 1398101, 178481, 5592405, 1082401][a-1]
    else:
        return (1<<a+1)-1

q = int(input())
for _ in range(q):
    a = int(input())
    print(calc(a))


q = int(input())
for i in range(q):
    a = int(input())
    a_bin = format(a, "b")
    if len(a_bin) == a_bin.count("1"):
        flag = 0
        for j in range(2, int(a**(1/2))+2):
            if a % j == 0:
                print(a//j)
                flag = 1
                break
        if flag == 0:
            print(1)
    else:
        print(2**(len(a_bin))-1)