Consider two non-negative long integers, $a$ and $\boldsymbol{b}$, where $a\leq b$. The bitwise AND of all long integers in the inclusive range between $a$ and $\boldsymbol{b}$ can be expressed as $a\ \text{&}\ (a+1)\ \text{&}\ \ldots\ \text{&}\ (b-1)\ \text{&}\ b$, where $\text{&}$ is the bitwise AND operator. 

Given $n$ pairs of long integers, $a[i]$ and $b[i]$, compute and print the bitwise AND of all natural numbers in the inclusive range between $a[i]$ and $b[i]$.

For example, if $\boldsymbol{a=10}$ and $b=14$, the calculation is $10\:\text{&}\:11\:\text{&}\:12\:\text{&}\:13\:\text{&}\:14=8$.  

Function Description  

Complete the andProduct in the editor below.  It should return the computed value as an integer.  

andProduct has the following parameter(s):  

a: an integer  
b: an integer  

Input Format

The first line contains a single integer $n$, the number of intervals to test. 

Each of the next $n$ lines contains two space-separated integers $a[i]$ and $b[i]$.

Constraints

$1\leq n\leq200$  
$0\leq a[i]\leq b[i]<2^{32}$

Output Format

For each pair of long integers, print the bitwise AND of all numbers in the inclusive range between $a[i]$ and $b[i]$ on a new line.

Sample Input 0
3
12 15
2 3
8 13

Sample Output 0
12
2
8

Explanation 0

There are three pairs to compute results for:

$\boldsymbol{a=12}$ and $\boldsymbol{b=15}$ 

$12~\text{&}~13~\text{&}~14~\text{&}~15~=12$, so we print $12$ on a new line.
$\boldsymbol{a}=2$ and $b=3$ 

$2\&3=2$
$\boldsymbol{a}=8$ and $b=13$ 

$8\:\text{&}\:9\:\text{&}\:10\:\text{&}\:11\:\text{&}\:12\&\:13\:=8$

Sample Input 1
2
17 23
11 15

Sample Output 1
16
8

Difficulty: MEDIUM
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:

Solutions:
T = int(input())
for _ in range(T):
	(A, B) = (int(_) for _ in input().split())
	(i, C) = (-1, A ^ B)
	while C > 0:
		C >>= 1
		i += 1
	print(A & 2 ** 32 - 2 ** i)


def longest_common_prefix(seq1, seq2):
	start = 0
	while start < min(len(seq1), len(seq2)):
		if seq1[start] != seq2[start]:
			break
		start += 1
	return seq1[:start]
t = int(input())
while t:
	s = input().split()
	(a, b) = (int(s[0]), int(s[1]))
	x = bin(a)[2:]
	y = bin(b)[2:]
	if len(x) < len(y):
		c = len(y) - len(x)
		while c:
			x = '0' + x
			c -= 1
	if len(y) < len(x):
		c = len(x) - len(y)
		while c:
			y = '0' + y
			c -= 1
	z = longest_common_prefix(x, y)
	if z == '':
		print('0')
	else:
		c = len(x) - len(z)
		while c:
			z = z + '0'
			c -= 1
		print(int(z, 2))
	t -= 1


for t in range(int(input())):
	(a, b) = sorted(map(int, input().split()))
	bits = ['0'] * (a.bit_length() + 1)
	for k in range(a.bit_length()):
		twoP = 1 << k
		if a & twoP and b < (a // twoP + 1) * twoP:
			bits[~k] = '1'
	ans = ''.join(bits)
	print(int(ans, 2))


import sys
t = int(sys.stdin.readline().strip())
for tests in range(t):
	(a, b) = [int(x) for x in sys.stdin.readline().split()]
	msb_a = 0
	msb_b = 0
	mask = 1 << 31
	a_test = True
	b_test = True
	if a == 0:
		msb_a = 0
		a_test = False
	if b == 0:
		msb_b = 0
		b_test = False
	while a_test or b_test:
		if mask & a != 0:
			msb_a = mask
			a_test = False
		if mask & b != 0:
			msb_b = mask
			b_test = False
		mask = mask >> 1
	if msb_b > msb_a:
		print(0)
	elif a % 2 == 0:
		print(a)
	else:
		print(msb_a)


def my_bin(n, length=32):
	t = str(bin(n))[2:]
	ans = '0' * (length - len(t)) + t
	return ans
for t in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	a = my_bin(a)
	b = my_bin(b)
	ans = [0] * 32
	for i in range(32):
		if a[i] == b[i]:
			ans[i] = a[i]
		else:
			break
	s = ''
	for i in ans:
		s += str(i)
	print(int(s, 2))


n = int(input())
while n > 0:
	n -= 1
	numbers = input().split()
	numbers = [int(x) for x in numbers]
	a = numbers[0]
	b = numbers[1]
	ans = 0
	i = 31
	while i >= 0:
		temp = 1
		temp = temp << i
		i -= 1
		if a & temp != 0 and b & temp == 0:
			break
		elif a & temp == 0 and b & temp != 0:
			break
		elif a & temp != 0 and b & temp != 0:
			ans = ans | 1 << i + 1
		else:
			continue
	print(ans)


import bisect
powers_of_2 = [2 ** x for x in range(32 + 1)]

def compute_and(A, B):
	if A <= 0:
		return 0
	min_pow = bisect.bisect_right(powers_of_2, A) - 1
	max_pow = bisect.bisect_right(powers_of_2, B) - 1
	if min_pow != max_pow:
		return 0
	if A == powers_of_2[min_pow]:
		return A
	tmp = 1 << min_pow
	return tmp + compute_and(A - tmp, B - tmp)
n_cases = int(input())
for _ in range(n_cases):
	(A, B) = (int(x) for x in input().split())
	if A == B:
		soln = A
	else:
		soln = compute_and(A, B)
	print(soln)


def calc(a, b):
	if a == 0 and b == 0:
		return 0
	if a == 1 and b == 1:
		return 1
	res = '0'
	for i in range(1, 32):
		if 2 ** i & a > 0:
			if b >= a + 2 ** i:
				res = '0' + res
			else:
				res = '1' + res
		else:
			res = '0' + res
	return int(res, 2)
t = int(input())
for _ in range(t):
	(a, b) = [int(x) for x in input().split()]
	print(calc(a, b))


import math

def round_down(n):
	if int(n) == n:
		return n
	else:
		return int(n)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 0 or b == 0 or int(math.log(a, 2)) < round_down(math.log(b, 2)):
		print(0)
	else:
		k = 0
		i = a
		j = a + 1
		while j <= b:
			a &= j
			k += 1
			j = i + 2 ** k
		a &= b
		print(a)


for T in range(int(input())):
	(A, B) = map(int, input().split())
	ans = 0
	for i in range(32):
		k = A + (1 << i) >> i
		if k << i >= B + 1 and k & 1 == 0:
			ans |= 1 << i
	print(ans)


def reduce_and(a, b):
	bits_to_ignore = (a - b).bit_length() - 1
	mask = 2 ** bits_to_ignore - 1
	a |= mask
	a ^= mask
	interval = 2 ** bits_to_ignore
	result = a
	for val in range(a, b + 1, interval):
		result &= val
	return result
count = int(input())
for i in range(count):
	(a, b) = [int(x) for x in input().split(' ')]
	print(reduce_and(a, b))


def solve(A, B):
	if A == B:
		return A
	(a, b, i, j) = (A, B, 0, 0)
	while a > 0 or b > 0:
		if (a ^ b) & 1:
			j = i
		a >>= 1
		b >>= 1
		i += 1
	return A & -2 ** j
T = int(input())
for _ in range(T):
	(A, B) = (int(_) for _ in input().split())
	print(solve(A, B))


from math import log, floor

def get_and(a, b):
	assert a <= b
	if a == b:
		return a
	if a + 1 == b:
		return a & b
	z = floor(log(b, 2))
	if a > 2 ** z:
		gap = b - a + 1
		while gap < 2 ** z:
			z -= 1
	assert z > 0
	return get_and(a >> z, b >> z) << z
t = int(input().strip())
for i in range(t):
	(a, b) = [int(x) for x in input().strip().split(' ')]
	print(get_and(a, b))


t = int(input().strip())
while t > 0:
	(a, b) = [int(i) for i in input().strip().split(' ')]
	count = 1
	while a != b:
		a = int(a / 2)
		b = int(b / 2)
		count *= 2
	t -= 1
	print(int(count * a))


def has_zero(a, b, n):
	if a & 2 ** n == 0:
		return True
	x = a // 2 ** n * 2 ** n
	x += 2 ** n
	return x <= b
for _ in range(int(input())):
	(a, b) = [int(s) for s in input().split()]
	res = 0
	for i in range(32):
		if not has_zero(a, b, i):
			res += 2 ** i
	print(res)


numcases = int(input())
for _ in range(numcases):
	(min, max) = [int(x) for x in input().split()]
	reverseDigits = []
	for i in range(32):
		place = pow(2, i)
		if place > max:
			break
		if min // place == max // place and min // place % 2 == 1:
			reverseDigits.append('1')
		else:
			reverseDigits.append('0')
	print(int(''.join(reversed(reverseDigits)), 2))


all_ones = pow(2, 33) - 1
n = int(input())
for i in range(n):
	(s, e) = [int(p) for p in input().split()]
	r = s
	twopow = 0
	v = pow(2, twopow)
	while twopow < 33:
		_next = (all_ones ^ v - 1) & s + v
		if v > e:
			break
		if _next <= e and r & v > 0:
			r ^= v
		twopow += 1
		v = pow(2, twopow)
	print(r)


for _ in range(int(input())):
	(A, B) = [int(i) for i in input().split()]
	v = A ^ B
	v |= v >> 1
	v |= v >> 2
	v |= v >> 4
	v |= v >> 8
	v |= v >> 16
	print(A & ~v)


def AND_A2B(A, B):
	if not A:
		return 0
	last1 = A & -A
	a = A - last1
	while a and a + (last1 << 1) <= B:
		last1 = a & -a
		a -= last1
	return 0 if not A and last1 << 1 <= B else a + last1

def bt4c(A, B):
	ans = A
	for i in range(A + 1, B + 1):
		ans &= i
	return ans
for _ in range(int(input())):
	(A, B) = map(int, input().split())
	print(AND_A2B(A, B))


T = int(input())
for _ in range(T):
	(A, B) = [int(x) for x in input().split()]
	a = bin(A)[2:]
	b = bin(B)[2:]
	if len(a) != len(b):
		print(0)
	else:
		i = 0
		while i < len(a):
			if a[i] != b[i]:
				break
			i += 1
		c = a[:i]
		while len(c) != len(a):
			c += '0'
		print(int(c, 2))


for _ in range(int(input())):
	(l, h) = [bin(int(x))[2:] for x in input().split()]
	if len(l) != len(h):
		print(0)
	elif l == h:
		print(int(l, 2))
	else:
		for i in range(1, len(l)):
			if l[i] != h[i]:
				print(int(l[:i] + '0' * (len(l) - i), 2))
				break


def hibit(n):
	n = n | n >> 1
	n = n | n >> 2
	n = n | n >> 4
	n = n | n >> 8
	n = n | n >> 16
	return n - (n >> 1)
T = int(input())
for _ in range(T):
	(A, B) = [int(i) for i in input().split()]
	diff = A ^ B
	diff = hibit(diff)
	diff = (diff << 1) - 1
	print(A & ~diff)


T = int(input())
for _ in range(T):
	(A, B) = (bin(int(i))[2:] for i in input().split())
	max_length = max(len(A), len(B))
	(A, B) = (x.zfill(max_length) for x in (A, B))
	i = 0
	result = ''
	while i < max_length and A[i] == B[i]:
		result += A[i]
		i += 1
	result += '0' * (max_length - i)
	print(int(result, 2))


t = int(input())
for ii in range(t):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	ax = str(bin(a))
	bs = str(bin(b))
	ca = len(ax)
	cb = len(bs)
	if ca == cb:
		c = ca
		aa = ax
		bb = bs
	elif ca > cb:
		c = ca
		aa = ax
		bb = '0'
		for i in range(1, ca - cb):
			bb += '0'
		bb += bs
	else:
		c = cb
		bb = bs
		aa = '0'
		for i in range(1, cb - ca):
			aa += '0'
		aa += ax
	ac = list(aa)
	bc = list(bb)
	xx = [0] * c
	i = 0
	while i < c:
		if ac[i] == bc[i]:
			xx[i] = ac[i]
			i += 1
		else:
			break
	for j in range(i, c):
		xx[j] = '0'
	ss = ''
	for i in range(c):
		ss += str(xx[i])
	print(int(ss, 2))


t = int(input())
for i in range(t):
	(a, b) = [int(x) for x in input().split()]
	x = a ^ b
	s = x >> 1
	while s != 0:
		x = x | s
		s >>= 1
	print(a & b & ~x)


T = int(input())
while T:
	(A, B) = map(int, input().split())
	if A == B:
		print(A)
		T -= 1
		continue
	(a, b) = map(bin, (A, B))
	dif = len(bin(B - A)[2:])
	(a, b) = (a[2:], b[2:])
	(x, y) = (len(a), len(b))
	if y > x:
		print(0)
		T -= 1
		continue
	ret = '0' * dif
	for z in range(dif + 1, x + 1):
		if a[-z] == '1' and b[-z] == '1':
			ret = '1' + ret
		else:
			ret = '0' + ret
	print(int(ret, 2))
	T -= 1


__author__ = 'mtadmk'
import sys

def pr(a):
	if db:
		print(a)

def process(a, b):
	act = a & b
	num = 1
	while a + num < b:
		act &= a + num
		num *= 2
	return act
db = False
if not db:
	n = int(input())
	for i in range(0, n):
		(a, b) = list(map(int, input().split()))
		print(process(a, b))
else:
	print(process(12, 15))
	print(process(2, 3))
	print(process(8, 13))


def and_product(a, b):
	b_str = bin(b)[2:]
	a_str = bin(a)[2:].zfill(len(b_str))
	result = []
	for i in range(len(b_str)):
		if a_str[i] == b_str[i]:
			result.append(b_str[i])
		else:
			break
	while len(result) != len(b_str):
		result.append('0')
	return int(''.join(result), 2)
t = int(input())
for _ in range(t):
	(a, b) = tuple(map(int, input().split()))
	print(and_product(a, b))


import math
T = int(input().strip())
for t in range(T):
	(a, b) = [int(x) for x in input().strip().split()]
	n = int(math.ceil(math.log(b, 2)))
	m = int(math.ceil(math.log(a ^ b, 2)))
	if m is 0:
		m = 1
	mask = (1 << n) - (1 << m)
	print(a & mask & b & mask)


def main():
	for _ in range(int(input())):
		(A, B) = map(int, input().split())
		A = bin(A)[2:]
		B = bin(B)[2:]
		answer = ''
		A = '0' * (32 - len(A)) + A
		B = '0' * (32 - len(B)) + B
		for i in range(32):
			if A[i] != B[i]:
				break
			answer += A[i]
		answer = answer + '0' * (32 - i)
		temp = 0
		for x in answer:
			if x == '1':
				break
		print(int(answer, base=2))
main()


def main():
	for _ in range(int(input())):
		(A, B) = map(int, input().split())
		A = bin(A)[2:]
		B = bin(B)[2:]
		answer = ''
		A = '0' * (32 - len(A)) + A
		B = '0' * (32 - len(B)) + B
		for i in range(32):
			if A[i] != B[i]:
				break
			answer += A[i]
		answer = answer + '0' * (32 - i)
		temp = 0
		for x in answer:
			if x == '1':
				break
		print(int(answer, base=2))
main()


for t in range(int(input())):
	(a, b) = map(int, input().split())
	s = a
	if b - a >= a:
		print(0)
	else:
		while a <= b:
			k = 1
			t = a
			while t % 2 == 0:
				t //= 2
				k *= 2
			a += k
			if a <= b:
				s &= a
		print(s)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	x = 0
	while A | x < B:
		x = x << 1 | 1
	print(A & ~x)


def function(start, end):
	blbs = bin(int(start))[2:]
	blbe = bin(int(end))[2:]
	if len(blbs) - len(blbe) == 0:
		k = 0
		while int(start) >> k != int(end) >> k:
			k += 1
		shift = int(start) >> k
		result = shift << k
		return result
	else:
		return 0
cases = int(input())
for case in range(cases):
	(a, b) = input().split()
	print(function(a, b))


a = 0
b = 0
c = 0
result = 0
current = 0
for i in range(0, int(input())):
	(a, b) = input().split()
	c = 0
	while int(a) | c < int(b):
		c = c << 1 | 1
	result = int(a) & ~c
	print(result)


t = int(input())
for uuhhhj in range(t):
	a = [int(i) for i in input().split()]
	p = bin(a[0])
	q = bin(a[1])
	m = min(len(p), len(q)) - 2
	p = p[-m:]
	q = q[-m:]
	s = '0b'
	t = 0
	for i in range(m):
		if p[i] != q[i] or t == 1:
			t = 1
			s += '0'
		else:
			s += p[i]
	print(int(s, 2))


import sys
import math

def bit_at_i(x, i):
	remainder = x % 2 ** (i + 1)
	if i == 0:
		return remainder
	if remainder:
		return int(math.log(remainder, 2 ** i))
	return 0
T = int(sys.stdin.readline())
for case in range(T):
	[A, B] = [int(X) for X in sys.stdin.readline().split()]
	ans = 0
	for i in range(int(math.log(B, 2)), -1, -1):
		bit_at_i_in_A = bit_at_i(A, i)
		bit_at_i_in_B = bit_at_i(B, i)
		if bit_at_i_in_A + bit_at_i_in_B == 2:
			ans += 2 ** i
		elif bit_at_i_in_A + bit_at_i_in_B == 1:
			break
	print(ans)


t = int(input())
for w in range(t):
	(start, end) = list((int(i) for i in input().split()))
	testLow = int.bit_length(start)
	testHigh = int.bit_length(end)
	if testHigh > testLow:
		print(0)
	else:
		result = start
		shift = 0
		while start <= end:
			while start & 1 == 0:
				start >>= 1
				end >>= 1
				result >>= 1
				shift += 1
			result &= start
			start += 1
		print(result << shift)


for _ in range(int(input())):
	(left, right) = list(map(int, input().split()))
	it = 0
	while left | it < right:
		it = it << 1 | 1
	print(left & ~it)


t = input()
t = int(t)
n = []
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	x = 0
	while n | x < m:
		x = x << 1 | 1
	print(n & ~x)


def and_product(a, b):
	l1 = len(a)
	l2 = len(b)
	b = b[l2 - l1:]
	i = 0
	res = ''
	while a[i] == b[i]:
		res += a[i]
		i += 1
	res += '0' * (l1 - i)
	return btd(res)

def dtb(n):
	ans = ''
	while n != 0:
		ans += str(n % 2)
		n = n // 2
	return ans[::-1]

def btd(S):
	num = 0
	l = len(S)
	for i in range(l - 1, -1, -1):
		if S[i] == '1':
			num += int(pow(2, l - 1 - i))
	return num
t = int(input())
for i in range(t):
	(a, b) = [int(j) for j in input().split()]
	if a * b == 0:
		print('0')
	else:
		print(and_product(dtb(a), dtb(b)))


def and_product(fst, secnd):
	fst = list(bin(fst))[2:]
	secnd = list(bin(secnd))[2:]
	if len(fst) != len(secnd):
		return 0
	num = 0
	same = True
	for ind in range(len(fst)):
		num *= 2
		same &= fst[ind] == secnd[ind]
		if same:
			num += int(fst[ind])
	return num
numtests = int(input())
for _ in range(numtests):
	print(and_product(*[int(s) for s in input().split()]))


def andProduct(A, B):
	shift_amount = 0
	while A != B:
		A = A >> 1
		B = B >> 1
		shift_amount += 1
	return A << shift_amount
T = int(input())
for _ in range(T):
	(A, B) = map(int, input().split(' '))
	print(andProduct(A, B))


def ANDprod(s):
	(n1, n2) = s.split()
	n1 = int(n1)
	n2 = int(n2)
	c1 = 0
	c2 = 0
	x = 1
	y = 1
	while x <= n1:
		x = x << 1 | 0
		c1 = c1 + 1
	while y <= n2:
		y = y << 1 | 0
		c2 = c2 + 1
	if x == y:
		y = 0
		while c1:
			c1 = c1 - 1
			x = x >> 1
			if x == x & n1 and x == x & n2:
				y = y ^ x
			elif 0 == x & n1 and 0 == x & n2:
				pass
			else:
				break
		return y
	else:
		return 0
t = int(input())
while t:
	s = input()
	res = ANDprod(s)
	print(res)
	t = t - 1


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	x = 0
	while A | x < B:
		x = x << 1 | 1
	print(A & ~x)


import fileinput
import math
for line in fileinput.input():
	values = line.split()
	if len(values) <= 1:
		pass
	else:
		left = int(values[0])
		right = int(values[1])
		if left == 0 or right == 0:
			print(0)
		else:
			res = ''
			i = 0
			while pow(2, i) <= left or pow(2, i) <= right:
				if round(math.floor(left / pow(2, i))) == round(math.floor(right / pow(2, i))):
					if left & pow(2, i) != 0:
						res = res + '1'
					else:
						res = res + '0'
				else:
					res = res + '0'
				i += 1
			res = res[::-1]
			print(int(res, 2))


from math import log2

def leftmost(n):
	shift = 1
	x = n
	while x > 1:
		x = n >> shift
		shift += 1
	return shift
T = int(input())
for t in range(0, T):
	(a, b) = [int(x) for x in input().split()]
	xor = a ^ b
	if xor != 0:
		lm = leftmost(a ^ b)
	else:
		lm = 0
	answer = (a >> lm & b >> lm) << lm
	print(answer)


t = int(input())
for i in range(t):
	(a, b) = input().split(' ')
	a = int(a)
	b = int(b)
	r = 0
	for j in range(32):
		if a == b and a & 1 == 1:
			r += 1 << j
		a >>= 1
		b >>= 1
	print(r)


t = int(input())
while t != 0:
	t -= 1
	(l, u) = map(int, input().split())
	s1 = '{0:032b}'.format(l)
	s2 = '{0:032b}'.format(u)
	s = [0] * 32
	i = 0
	flag = False
	ans = 0
	while i < 32:
		if s2[i] == '1' and s1[i] == '1':
			s[i] = 1
			flag = True
		if flag == True and (s1[i] == '1' and s2[i] == '0' or (s1[i] == '0' and s2[i] == '1')):
			break
		i += 1
	i = 0
	s.reverse()
	while i != 32:
		ans += s[i] * pow(2, i)
		i += 1
	print(ans)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	x = 0
	while A | x < B:
		x = x << 1 | 1
	print(A & ~x)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = 0
	while a | x < b:
		x = x + x | 1
	print(a & ~x)


def calc_and(a, b):
	result = 0
	distance = b - a + 1
	for i in range(0, 32):
		if distance <= 1 << i:
			mask = 1 << i
			if a & mask == b & mask:
				result = result | a & mask
	return result

def main():
	T = int(input())
	for t in range(0, T):
		var = input().split()
		a = int(var[0])
		b = int(var[1])
		print(calc_and(a, b))
main()


tests = int(input())
for i in range(tests):
	bounds = input().split(' ')
	m = int(bounds[0])
	n = int(bounds[1])
	bitcount = 0
	while m != n:
		m = m >> 1
		n = n >> 1
		bitcount += 1
	print(m << bitcount)


def and_product(start, end):
	result = start
	steps = end - start
	i = 0
	while start >> i > 0:
		if lmask(start, i + 1) + steps > lmask(-1, i + 1):
			result = bitmask(result, i)
		i += 1
	return result

def lmask(n, k):
	return n & (1 << k) - 1

def bitmask(n, k):
	return n & (-1 << k + 1 | lmask(-1, k))

def main():
	k = int(input())
	for _ in range(k):
		(start, end) = input().split()
		print(and_product(int(start), int(end)))
main()


numOfCase = int(input())
for noc in range(numOfCase):
	l = list(map(lambda s: int(s), input().split(' ')))
	m = l[0]
	n = l[1]
	res = n
	while res > m:
		res = res & res - 1
	print(res)


for _ in range(int(input())):
	(a, b) = [int(i) for i in input().strip().split()]
	diff = b - a
	n = 0
	while diff:
		diff >>= 1
		n += 1
	res = (a & b) >> n << n
	print(res)


for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	(a, b) = (bin(a)[2:], bin(b)[2:])
	if len(a) != len(b):
		print(0)
	else:
		res = 0
		for i in range(len(a)):
			if a[i] == b[i] == '1':
				res |= 1 << len(a) - i - 1
			elif a[i] == '0' and b[i] == '1':
				break
		print(res)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	result = 1
	(aBinary, bBinary) = (bin(a)[2:], bin(b)[2:])
	aBinary = '0' * (len(bBinary) - len(aBinary)) + aBinary
	result = ''
	for i in range(len(aBinary)):
		if aBinary[i] == bBinary[i]:
			result += aBinary[i]
		else:
			result += '0'
			break
	i += 1
	result = result + '0' * (len(bBinary) - i)
	print(int(result, 2))


from functools import reduce
cases = int(input().strip())
for case in range(cases):
	(start, end) = (int(x) for x in input().strip().split(' '))
	x = start ^ end
	s = x // 2
	while s > 0:
		x |= s
		s //= 2
	print(start & end & ~x)


T = int(input())
for _ in range(T):
	(A, B) = map(int, input().split())
	i = 0
	while 2 ** i < B - A:
		i += 1
	ans = A & B & (4294967295 ^ 2 ** i - 1)
	print(ans)


import math
numcases = int(input())
while numcases > 0:
	[a, b] = list(map(lambda x: int(x), input().split(' ')))
	this = a & b
	if this == 0:
		print(0)
		numcases -= 1
		continue
	that = list(map(lambda x: int(x), list('{0:b}'.format(this))))
	that.reverse()
	first = list(map(lambda x: int(x), list('{0:b}'.format(a))))
	first.reverse()
	second = list(map(lambda x: int(x), list('{0:b}'.format(b))))
	second.reverse()
	if len(first) != len(second):
		print(0)
		numcases -= 1
		continue
	answer = 0
	while first != []:
		temp1 = first.pop()
		temp2 = second.pop()
		if temp1 == temp2:
			if temp1 == 1:
				answer += 2 ** len(first)
			continue
		else:
			break
	print(answer)
	numcases -= 1


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	x = 0
	while A | x < B:
		x = x << 1 | 1
	print(A & ~x)


for t in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	a = bin(a)[2:]
	b = bin(b)[2:]
	sol = 0
	if len(a) != len(b):
		print(0)
	else:
		i = 0
		while a[i] == b[i]:
			if a[i] == '1':
				sol += 2 ** (len(a) - i - 1)
			i += 1
			if i == len(a):
				break
		print(sol)


from functools import reduce
for t in range(int(input().strip())):
	(a, b) = map(int, input().strip().split())
	ans = 0
	found_one = False
	for i in range(31, -1, -1):
		if a & 2 ** i ^ b & 2 ** i and found_one:
			break
		elif a & 2 ** i & (b & 2 ** i):
			found_one = True
			ans += 2 ** i
	print(ans)


t = int(input())
for i in range(0, t):
	s = input()
	ss = s.split(' ')
	a = int(ss[0])
	b = int(ss[1])
	pow = 0
	while 1:
		if 2 ** pow > a:
			break
		else:
			pow = pow + 1
	if 2 ** pow > b and 2 ** (pow - 1) < b:
		aa = '{0:b}'.format(a)
		bb = '{0:b}'.format(b)
		if len(aa) < len(bb):
			str_add = ''
			for ii in range(0, len(bb) - len(aa)):
				str_add = str_add + '0'
			aa = aa + str_add
		if len(aa) > len(bb):
			str_add = ''
			for ii in range(0, len(aa) - len(bb)):
				str_add = str_add + '0'
			bb = bb + str_add
		fin_ans = ''
		for ii in range(0, len(aa)):
			if aa[ii] == bb[ii]:
				fin_ans = fin_ans + aa[ii]
			else:
				break
		for ii in range(0, len(aa) - len(fin_ans)):
			fin_ans = fin_ans + '0'
		print(int(fin_ans, 2))
	else:
		print('0')


def next_all_ones(n):
	n -= 1
	for k in (1, 2, 4, 8, 16, 32, 64):
		n |= n >> k
	return n
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	print(a & b & ~next_all_ones(a ^ b))


T = int(input().strip())
for _ in range(T):
	(a, b) = [int(s) for s in input().strip().split(' ')]
	et = a & b
	for i in range(et.bit_length()):
		bit = 1 << i
		if et & bit:
			if a <= b - bit:
				et -= bit
	print(et)


T = int(input())
for _ in range(T):
	(l, r) = [int(i) for i in input().split()]
	x1 = x2 = l ^ r
	while x1:
		x1 >>= 1
		l >>= 1
	while x2:
		x2 >>= 1
		l <<= 1
	print(l)


import sys
n = int(sys.stdin.readline().strip())
for i in range(n):
	cl = [int(num) for num in sys.stdin.readline().strip().split(' ')]
	x = 0
	while cl[0] | x < cl[1]:
		x = x << 1 | 1
	print(cl[0] & ~x)


t = int(input())
for k in range(t):
	(a, b) = map(int, input().split(' '))
	x = 0
	while a | x < b:
		x <<= 1
		x |= 1
	print(a & ~x)


T = int(input())
for _ in range(T):
	(A, B) = tuple([int(token) for token in input().split()])
	diff = A ^ B
	diff = diff | diff >> 1
	diff = diff | diff >> 2
	diff = diff | diff >> 4
	diff = diff | diff >> 8
	diff = diff | diff >> 16
	R = A & B & ~diff
	print(R)


author = 'Ashu'
tc = int(input())
for _ in range(tc):
	x = input().split()
	a = int(x[0])
	b = int(x[1])
	r = 0
	while a | r < b:
		r = r << 1 | 1
	print(a & ~r)


T = int(input())
for T_i in range(T):
	(p, r) = [int(x) for x in input().split()]
	if len(bin(p)) != len(bin(r)):
		print(0)
		continue
	low = bin(p)[2:]
	high = bin(r)[2:]
	ans = 0
	for c in range(len(low)):
		if low[c] == high[c] == '1':
			ans += 2 ** (len(low) - c - 1)
		elif low[c] != high[c]:
			break
	print(ans)


import math
t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	count = 0
	while a.bit_length() == b.bit_length():
		highest_pow = int(math.pow(2, a.bit_length() - 1))
		count += highest_pow
		a -= highest_pow
		b -= highest_pow
	print(count)


for _ in range(int(input())):
	(a, b) = (int(f) for f in input().split())
	result = 0
	bit = 1
	while bit <= b:
		if bit & a & b:
			result |= bit
		elif bit & a != bit & b:
			result = 0
		bit <<= 1
	print(result)


t = int(input())
while t:
	(a, b) = [int(i) for i in input().split()]
	ans = b
	k = 0
	i = a
	while i < b:
		ans &= i
		i += 2 ** k
		k += 1
	print(ans)
	t -= 1


def bin_repr(n):
	return '{:b}'.format(n)

def smart(low, high):
	return int(_smart_r(bin_repr(low), bin_repr(high)), base=2)

def _smart_r(low_bin_str, high_bin_str):
	low_bin_str_stripped = low_bin_str.lstrip('0')
	high_bin_str_stripped = high_bin_str.lstrip('0')
	if len(low_bin_str) == 0:
		return ''
	if len(low_bin_str_stripped) != len(high_bin_str_stripped):
		return '0' * len(high_bin_str)
	else:
		return low_bin_str[0] + _smart_r(low_bin_str[1:], high_bin_str[1:])

def main():
	test_count = int(input())
	for __ in range(test_count):
		(low, high) = [int(x) for x in input().split(' ')]
		print(smart(low, high))
main()


T = int(input())
for _ in range(0, T):
	(S, L) = map(int, input().split())
	if S == 0 or L == 0:
		print(0)
		continue
	S = '{0:032b}'.format(S)
	L = '{0:032b}'.format(L)
	S = list(S)
	L = list(L)
	S.reverse()
	L.reverse()
	s = S.pop()
	l = L.pop()
	while s != '1' and l != '1' and S:
		s = S.pop()
		l = L.pop()
	ans = []
	if len(S) > 0:
		ans.append('1')
		s = S.pop()
		l = L.pop()
		while s == l and S:
			ans.append(s)
			s = S.pop()
			l = L.pop()
		ans.append('0')
		for i in S:
			ans.append('0')
		print(int(''.join(ans), 2))
	else:
		print(0)


import math

def AndAll(start, end):
	s = start
	zeros_from_right = int(math.log(end - start, 2)) + 1
	s = s >> zeros_from_right
	s = s << zeros_from_right
	return s & end

def main():
	T = int(input())
	for i in range(T):
		R = input().split(' ')
		start = int(R[0])
		end = int(R[1])
		print(AndAll(start, end))
main()


import sys
T = int(input().strip())

def ANDproduct(A, B):
	s = (B ^ A).bit_length()
	B = B >> s
	B = B << s
	return B
for t in range(T):
	arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	print(ANDproduct(arr[0], arr[1]))


def test_case():
	(m, n) = [int(x) for x in input().split()]
	k = 0
	while True:
		if n > m:
			k += 1
		else:
			return m << k
		m = m >> 1
		n = n >> 1

def main():
	T = int(input())
	while T > 0:
		print(test_case())
		T -= 1
main()


__author__ = 'siddharth'
from math import floor, log2
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	if min(m, n) == 0:
		print(0)
		continue
	x = floor(log2(m ^ n)) + 1
	y = floor(log2(min(m, n))) + 1
	z = 2 ** y - 2 ** x
	print(m & z)


for _ in range(int(input())):
	(a, b) = (int(x) for x in input().split())
	r = 0
	for i in range(32, -1, -1):
		bit = 2 ** i
		if a & bit == b & bit:
			r += a & bit
		else:
			break
	print(r)


import math

def andProduct(min, max):
	total = 0
	while min != 0 and max != 0 and (math.floor(math.log(min, 2)) == math.floor(math.log(max, 2))):
		mvb = math.floor(math.log(min, 2))
		total += 1 << mvb
		min = min & ~(1 << mvb)
		max = max & ~(1 << mvb)
	return int(total)
rounds = int(input())
for i in range(rounds):
	(min, max) = map(int, input().split())
	print(andProduct(min, max))


from math import log
for caseNum in range(int(input())):
	(a, b) = map(int, input().split())
	print(a & b & ~((1 << int(1 + log(b - a, 2))) - 1))


def andpro(A, B):
	lenA = len('{0:b}'.format(A))
	lenB = len('{0:b}'.format(B))
	if lenA == lenB:
		i = 0
		strA = '{0:b}'.format(A)
		strB = '{0:b}'.format(B)
		curr = ''
		for i in range(lenA):
			if strA[i] == strB[i]:
				curr += strA[i]
			else:
				break
		curr = curr + '0' * (lenA - len(curr))
		print(int(curr, 2))
		return
	else:
		print('0')
		return
t = int(input())
for _ in range(t):
	(A, B) = [int(x) for x in input().strip().split(' ')]
	andpro(A, B)


def bitLen(int_type):
	length = 0
	while int_type:
		int_type >>= 1
		length += 1
	return length
T = int(input())
for j in range(T):
	(A, B) = input().split(' ')
	A = int(A)
	B = int(B)
	result = 0
	lengthA = bitLen(A)
	lengthB = bitLen(B)
	while lengthA == lengthB:
		temp = 1
		for i in range(lengthA - 1):
			temp <<= 1
		result |= temp
		A = A & ~temp
		B = B & ~temp
		lengthA = bitLen(A)
		lengthB = bitLen(B)
	print(result)


def run(a, b):
	if len(bin(b)) > len(bin(a)):
		return 0
	d = len(bin(b - a)) - 2
	(a_, b_) = (int(bin(a)[:-d], 2), int(bin(b)[:-d], 2))
	s = a_
	for x in range(a_ + 1, b_ + 1):
		s &= x
	return s * 2 ** d
for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	print(run(a, b))


def min_and(a, b):
	for i in range(a.bit_length(), -1, -1):
		mask = 2 ** i
		if a & mask != b & mask:
			return sum((a & 2 ** j for j in range(i + 1, a.bit_length())))
	return a & a + 1
test_cases = int(input().strip())
for _ in range(test_cases):
	(a, b) = [int(n) for n in input().strip().split()]
	if a.bit_length() != b.bit_length():
		result = 0
	else:
		result = min_and(a, b)
	print(result)


from math import log
t = int(input())
for _ in range(t):
	(a, b) = [int(x) for x in input().split()]
	c = b - a
	if c == 0:
		print(a)
	else:
		d = 2 ** (int(log(c, 2)) + 1) - 1
		print(a & b & (4294967295 ^ d))


for _ in range(int(input())):
	(A, B) = map(int, input().split())
	N = A.bit_length()
	if N == B.bit_length():
		(A, B) = (str(bin(A))[2:], str(bin(B))[2:])
		for i in range(N):
			if not A[i] == B[i]:
				print(int(A[:i] + '0' * (N - i), 2))
				break
	else:
		print(0)


T = int(input().strip())
for t in range(0, T):
	(a, b) = list(map(int, input().strip().split(' ')))
	(A, B) = [bin(a)[2:], bin(b)[2:]]
	(alen, blen) = (len(A), len(B))
	if alen < blen:
		print(0)
	else:
		s = ''
		found = False
		for i in range(0, alen):
			if found:
				s += '0'
			elif A[i] == '0':
				if B[i] == '1':
					found = True
				s += '0'
			else:
				s += '1'
		bwAND = int(s, 2)
		print(bwAND)


for t in range(int(input())):
	(a, b) = map(int, input().split())
	answer = a
	for i in range(32):
		d = 1 << i
		if a & d and (not b & d or b - a >= d):
			answer ^= d
	print(answer)


t = int(input())
for tt in range(t):
	(a, b) = list(map(int, input().split()))
	a_b = list(bin(a)[2:])
	b_b = list(bin(b)[2:])
	if len(a_b) > len(b_b):
		b_b = [0] * (len(a_b) - len(b_b)) + b_b
	else:
		a_b = [0] * (len(b_b) - len(a_b)) + a_b
	res = []
	for (i, (bit_a, bit_b)) in enumerate(zip(a_b, b_b)):
		if bit_a == bit_b:
			res.append(bit_a)
		else:
			res += [0] * (len(a_b) - i)
			break
	print(int(''.join((str(x) for x in res)), 2))


T = int(input())
for _ in range(T):
	(A, B) = map(lambda x: bin(int(x)), input().split())
	ans = ''
	for (ind, digit) in enumerate(A):
		if ind < 2:
			continue
		if digit == B[ind]:
			ans += digit
		else:
			ans += '0' * (len(B) - ind)
			break
	print(int(ans, 2))