Recently Luba learned about a special kind of numbers that she calls beautiful numbers. The number is called beautiful iff its binary representation consists of k + 1 consecutive ones, and then k consecutive zeroes.

Some examples of beautiful numbers:   1_2 (1_10);  110_2 (6_10);  1111000_2 (120_10);  111110000_2 (496_10). 

More formally, the number is beautiful iff there exists some positive integer k such that the number is equal to (2^{k} - 1) * (2^{k} - 1).

Luba has got an integer number n, and she wants to find its greatest beautiful divisor. Help her to find it!


-----Input-----

The only line of input contains one number n (1 ≤ n ≤ 10^5) — the number Luba has got.


-----Output-----

Output one number — the greatest beautiful divisor of Luba's number. It is obvious that the answer always exists.


-----Examples-----
Input
3

Output
1

Input
992

Output
496

Difficulty: interview

Starter code:

Solutions:
from collections import Counter, defaultdict
import itertools
import sys

def main():
    n = int(input())
    ans = 1
    for k in range(1, 10):
        v = ((1 << k) - 1) * (1 << (k - 1))
        if n % v == 0:
            ans = v

    print(ans)

main()


n = int(input())
mx = 1

def check(v):
    s = bin(v)[2:]
    k = s.count('1')
    if ('1' * k + '0' * (k - 1)) == s:
        return 1
    return 0

for i in range(1, n + 1):
    if n % i:
        continue
    if check(i) and i > mx:
        mx = i
print(mx)



n = int(input())

for k in range(20, 0, -1):
    div = (2**k - 1) * (2**(k - 1))
    if n % div == 0:
        print(div)
        break


def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())

b = [((1 << (k+1)) - 1) << k for k in range(10)]
b.reverse()
n = ii()
for x in b:
    if n % x == 0:
        print(x)
        break

n = []
for x in range(1,10):
	n += [(2 ** x - 1) * (2 ** (x - 1))]
x = int(input())
k = []
for i in range(9):
	if x % n[i] == 0:
		k += [n[i]]
print(max(k))


ar=[(pow(2,x)-1)*pow(2,x-1) for x in range(1,100)]
n=int(input())
mx=1
for x in ar:
    if n%x==0:
        mx=x
print(mx)

n=int(input())
m=[1]
k=2
while m[-1]<n:
    m.append((2**k-1)*(2**(k-1)))
    k+=1
for x in reversed(m):
    if n%x==0:
        print(x)
        break


from sys import stdin, stdout

n = int(stdin.readline())
dividers = []
sze = 20

for i in range(1, sze):
    v = ((1 << i) - 1) * (1 << (i - 1))
    dividers.append(v)

for v in dividers[::-1]:
    if not n % v:
        stdout.write(str(v))
        break

n = int(input())
for elem in [523776, 130816, 32640, 8128, 2016, 496, 120, 28, 6, 1]:
    if n % elem == 0:
        print(elem)
        break

n = int(input())
k = 1
t = 1
maxt = 1
while t <= n:
    k += 1
    t = (2 ** k - 1) * (2 ** (k - 1))
    if n % t == 0:
        maxt = t
print(maxt)

import itertools
import re
import math
import getpass
import sys
import string

debug = getpass.getuser() == 'frohe'
files = True

if debug and files:
    sys.stdin = open('test.in')
else:
    pass
    # sys.stdin = open('schools.in')
    # sys.stdout = open('schools.out', 'w')


def ria():
    return [int(i) for i in input().split()]

n=ria()[0]
ar = []
for i in range(1, 30):
    ar.append(int('1' * i + '0' * (i - 1),2))
#print(ar)
for i in reversed(ar):
    if n%i==0:
        print(i)
        return


n = int(input())

ans = 1
for i in range(2,n+1):
    for k in range(1,18):
        x = (2 ** k - 1) * (2 ** (k-1))
        if n % x == 0:
            ans = x

print(ans)


q=int(input())
a=[1, 6, 28, 120, 496, 2016, 8128, 32640, 130816]
s=0
for i in a:
    if q%i==0:
        s=i
print(s)


def solve(n):
    maxx = len(bin(n)[2:])
    if not maxx & 1:
        maxx -= 1

    while maxx > 1:
        beaut = int('1'*((maxx//2 + 1)) + '0' * (maxx//2), 2)
        if n % beaut == 0:
            return beaut

        maxx -= 2

    return 1

print(solve(int(input())))

cur = '1'
beautiful = [int(cur, 2),]
while int(cur, 2) < 1e5:
    cur = '1' + cur + '0'
    beautiful.append(int(cur, 2))
# print(beautiful)
n = int(input())
for x in beautiful[::-1]:
    if n % x == 0:
        print(x)
        break



n=int(input())
l=[]
k=1
num=0
while num<=100000:
    num=((2**k)-1)*(2**(k-1))
    if num<=100000:
        l.append(num)
    k+=1
ans=1
for each in l:
    if n%each==0:
        ans=each
print(ans)


n = int(input())
for i in range(n, 0, -1):
    if n % i != 0:
        continue
    bz = f'{i:b}'
    if bz.count('0') + 1 != bz.count('1'):
        continue
    elif set(bz[:len(bz)//2 + 1]) == {'1'}:
        print(i)
        break



def divisor(k):
    return (2 ** k - 1) * (2 ** (k - 1))


k = int(input().strip().split()[0])
answer = 1
for i in range(1, k):
    if divisor(i) > k:
        break
    else:
        if k % divisor(i) == 0:
            answer = divisor(i)
print(answer)

n = int(input())

s = "{0:b}".format(n)
l = len(s)

for k in range(int(l/2), -1, -1):
    b = ''.join(['1']*(k+1) + ['0']*k)
    n2 = int(b,2)
    if n2 <= n and n % n2 == 0:
        print(n2)
        break




def main():
	n = int(input());
	k = 1;
	num = 1;
	ans = 1;
	while(num<=n):
		num = (2**k - 1) * (2 ** (k-1))
		if(n%num==0): ans = num
		k+=1
	print(ans);

main()

n = int(input())
for i in range(8, -1, -1):
    b = ((2**(i+1)) - 1)*(2**i)
    if n % b == 0:
        print(b)
        return

import math
a=[]
for k in range(1,12):
    # print(math.pow(2,k) - 1)
    a.append((int(math.pow(2,k))-1) * int(math.pow(2,k-1)))

a=a[::-1]
n=int(input())
for i in a:
    if n%i==0:
        print(i)
        break


n = int(input())
a = []
tmp = 0
k = 1
while tmp * 2 < n:
    tmp = (2**k - 1) * (2**(k - 1))
    a.append(tmp)
    k += 1
for i in range(len(a) - 1, -1, -1):
    if n % a[i] == 0:
        print(a[i])
        return


n=int(input())
num=1
k=2
l=[1]
while num<n :
    num=(2**k-1)*(2**(k-1))
    if n%num==0 :
        l.append(num)
    k+=1
print(l[-1])