Let's denote as $\text{popcount}(x)$ the number of bits set ('1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l ≤ x ≤ r, and $\text{popcount}(x)$ is maximum possible. If there are multiple such numbers find the smallest of them.


-----Input-----

The first line contains integer n — the number of queries (1 ≤ n ≤ 10000).

Each of the following n lines contain two integers l_{i}, r_{i} — the arguments for the corresponding query (0 ≤ l_{i} ≤ r_{i} ≤ 10^18).


-----Output-----

For each query print the answer in a separate line.


-----Examples-----
Input
3
1 2
2 4
1 10

Output
1
3
7



-----Note-----

The binary representations of numbers from 1 to 10 are listed below:

1_10 = 1_2

2_10 = 10_2

3_10 = 11_2

4_10 = 100_2

5_10 = 101_2

6_10 = 110_2

7_10 = 111_2

8_10 = 1000_2

9_10 = 1001_2

10_10 = 1010_2

Difficulty: competition

Starter code:

Solutions:
def popcount(n):
	res = 0
	while n > 0:
		res += n & 1
		n >>= 2

def A(l, r):
	r += 1
	t = 1 << 64
	while t & (l ^ r) == 0:
		t >>= 1
	res = l | (t - 1)
	#print(t, res)
	return res

def __starting_point():
	"""assert(A(1, 2) == 1)
	assert(A(2, 4) == 3)
	assert(A(1, 10) == 7)
	assert(A(13, 13) == 13)
	assert(A(1, 7) == 7)"""

	n = int(input())
	for _ in range(n):
		l, r = list(map(int, input().split()))
		res = A(l, r)
		print(res)

__starting_point()

for i in range(int(input())):
 l,r=list(map(int,input().split()))
 while(l|(l+1)<=r): l|=l+1
 print(l)


from math import log2
def solve(a, b):
    if a == b:
        return a
    x = int(log2(b))
    if 2**x <= a:
        return solve(a - 2**x, b - 2**x) + 2**x

    if 2**(x+1) - 1 <= b:
        return 2**(x+1) - 1

    return 2**x - 1

x = int(input())
for i in range(x):
    a, b = list(map(int, input().split(' ')))
    print(solve(a, b))


def main():
    for _ in range(int(input())):
        l, r = list(map(int, input().split()))
        mask = 1
        while l <= r:
            x = l
            l |= mask
            mask <<= 1
        print(x)


def __starting_point():
    main()

__starting_point()

n=int(input())
while(n):
    n=n-1
    s=input()
    li=s.split(' ')
    l=int(li[0])
    r=int(li[1])
    ans=r
    while(r>=l):
        ans=r
        r=r&(r+1)
        r=r-1
    print(ans)


def solve():
	a, b = [int(x) for x in input().split()]
	l = b - a + 1
	for i in range(64):
		if a & (1 << i):
			continue
		if (a | (1 << i)) > b:
			break
		a |= 1 << i
	print(a)

n = int(input())
for i in range(n):
	solve()


# 484A

from sys import stdin

__author__ = 'artyom'

n = int(stdin.readline().strip())
for i in range(n):
  l, r = list(map(int, stdin.readline().strip().split()))
  x, p = l, 1
  while 1:
    x |= p
    if x > r:
      break
    p = p << 1 | 1
    l = x

  print(l)

def f():
    l, r = map(int, input().split())
    if l == r: return l
    a, b = bin(l)[2:], bin(r)[2:]
    i, k = 0, len(b)
    a = a.zfill(k)
    while a[i] == b[i]: i += 1
    d = k - i
    if b[i:].count('1') == d: return r
    return ((r >> d) << d) + (1 << d - 1) - 1

for i in range(int(input())): print(f())

for i in range(int(input())):
    l, r = map(int, input().split())
    if l == r: print(l)
    else:
        k = len(bin(l ^ r)) - 2
        s = ((r >> k) + 1 << k) - 1
        if s > r: s -= 1 << k - 1
        print(s)

for i in range(int(input())):
    l, r = map(int, input().split())
    k = 0 if l == r else len(bin(l ^ r)) - 2
    s = ((r >> k) + 1 << k) - 1
    if s > r: s -= 1 << k - 1
    print(s)

import math
def f(l,r):
    if l == r:
        return l
    else:
        b = int(math.log(r,2))
        if p[b] <= l:
            return f(l-p[b],r-p[b])+p[b]
        elif p[b+1]-1 <= r:
            return p[b+1]-1
        else:
            return p[b]-1
p = [1]
for i in range(64):
    p.append(p[-1]*2)
n = int(input())
for i in range(n):
    l, r = [int(i) for i in input().split()]
    print(f(l,r))


n = int(input())
for i in range(n):
    a, b = list(map(int, input().split()))
    m = a; bits = str(a).count('1')
    x = 0
    while a <= b:
        a |= (1 << x)
        z = bin(a).count('1')
        if z > bits and a <= b:
            m = a
            bits = z
        elif z == bits and a < m:
            m = a
        x += 1
    print(m)


n = int(input())

for i in range(n):
	l, r = list(map(int, input().split()))
	bits = 0
	result = 0
	while True:
		count_bit = len(str(bin(r))) - 2
		if (1 << count_bit) - 1 == r:
			result += (1 << count_bit) - 1
			break
		exp = (1 << (count_bit - 1)) - 1
		if exp >= l:
			result += exp
			break
		else:
			bits += 1
			exp = 1 << (count_bit - 1)
			result += exp
			l -= exp
			r -= exp
	print(result)


import sys
L = lambda x : len(bin(x)) - 2
n = int(input())
while n > 0:
    n -= 1
    l, r = list(map(int, sys.stdin.readline().split()))
    a = 0
    while L(l) == L(r) and  r > 0:
        u = 1 << (L(r) - 1)
        l-= u
        r-= u
        a+= u
    u = 1 << (L(r) - 1)
    if u + u - 1 == r and r > 1:
        u<<=1
    print(a+u-1)



import sys
L = lambda x : x.bit_length() if x > 0 else 1
n = int(input())
while n > 0:
    n -= 1
    l, r = list(map(int, sys.stdin.readline().split()))
    a = 0
    while L(l) == L(r) and  r > 0:
        u = 1 << (L(r) - 1)
        l-= u
        r-= u
        a+= u
    u = 1 << (L(r) - 1)
    if u + u - 1 == r and r > 1:
        u<<=1
    print(a+u-1)



def fun(x,y):
    if x==y:
        return x
    if (y&(y+1)) == 0:
        return y
    [a,b] = [len(bin(x))-3,len(bin(y))-3]
    if a==b:
        return (1<<a)| fun((1<<a)^x, (1<<a)^y)
    return (1<<b) - 1
    
def main():
    mode="filee"
    if mode=="file":f=open("test.txt","r")
    get = lambda :[int(x) for x in (f.readline() if mode=="file" else input()).split()]
    [n]=get()
    for z in range(n):
        [x,y]=get()
        print(fun(x,y))


    if mode=="file":f.close()


def __starting_point():
    main()

__starting_point()

for i in range(int(input())):
 l,r=list(map(int,input().split()))
 while(l|(l+1)<=r): l|=l+1
 print(l)


for i in range(int(input())):
 l,r=map(int,input().split())
 while(l|(l+1)<=r): l|=l+1
 print(l)

def get_near_power_of_two(x):
    b = 1
    while b <= x:
        b <<= 1
    return b >> 1

n = int(input())
for _ in range(n):
    l, r = list(map(int, input().split()))
    xor = l ^ r
    d = get_near_power_of_two(xor) - (0 if xor == 0 else 1)
    ld = l | d
    rd = r | d
    print(rd if rd == r else ld)


n = int(input())
for kase in range(n):
    l, r = map(int, input().split())
    bit = 0
    while l | (1 << bit) <= r:
        l = (l | (1 << bit))
        bit += 1
    print(l)

n=int(input())
for j in range(0,n):
	l,r=map(int,input().split(" "))
	while(l|(l+1)<=r):
		l=l|(l+1)
	print(l)

q=int(input())
for i in range(q):
    x,y=list(map(int,input().split()))
    diff=y-x
    x=bin(x)[2:]
    y=bin(y)[2:]
    x='0'*(len(y)-len(x))+x
    newString=''
    for j in range(len(x)):
        if x[len(x)-j-1]=='0':
            if diff>=2**j:
                newString+='1'
                diff-=2**j
            else:
                newString+='0'
        else:
            newString+='1'
    newString=newString[::-1]
    tot=0
    ns=len(newString)
    for i in range(ns):
        tot+=int(newString[ns-i-1])*(2**i)
    print(tot)


import sys
#sys.stdin = open("input", "r")
n = int(input())
for x in range(n):
   l, r = list(map(int, input().split()))
   a = 0
   while l <= r:
      a = l
      l += (~l) & (-~l)
   sys.stdout.write(str(a) + '\n')


def get(l, r):
    while l | (l + 1) <= r:
        l |= (l + 1)
    return l

q = int(input())
for i in range(q):
    l, r = list(map(int, input().split()))
    print(get(l, r))


def maxi(a,b):
	if(bin(a).count("1")==bin(b).count("1")):
		return(min(a,b))	
	elif(bin(a).count("1")>bin(b).count("1")):
		return a
	else:
		return b
t=int(input().rstrip())
for i in range(t):
	a,b=list(map(int,(input().rstrip().split(" "))))
	x=bin(a)[2:]
	y=bin(b)[2:]
	w=max(len(x),len(y))
	x="0"*(w-len(x))+x
	y="0"*(w-len(y))+y
	q=[0 for i in range(w)]
	for j in range(w):
		if(x[j]!=y[j]):
			q[j]="0"
			break
		else:
			q[j]=x[j]
	for o in range(j+1,w):
		q[o]="1"
	e=int("0b"+"".join(q),2)
	print(maxi(e,b))