You are given an array consisting of all integers from $[l, r]$ inclusive. For example, if $l = 2$ and $r = 5$, the array would be $[2, 3, 4, 5]$. What's the minimum number of elements you can delete to make the bitwise AND of the array non-zero?

A bitwise AND is a binary operation that takes two equal-length binary representations and performs the AND operation on each pair of the corresponding bits.


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then $t$ cases follow.

The first line of each test case contains two integers $l$ and $r$ ($1 \leq l \leq r \leq 2 \cdot 10^5$) — the description of the array.


-----Output-----

For each test case, output a single integer — the answer to the problem.


-----Examples-----

Input
5
1 2
2 8
4 5
1 5
100000 200000
Output
1
3
0
2
31072


-----Note-----

In the first test case, the array is $[1, 2]$. Currently, the bitwise AND is $0$, as $1\ \& \ 2 = 0$. However, after deleting $1$ (or $2$), the array becomes $[2]$ (or $[1]$), and the bitwise AND becomes $2$ (or $1$). This can be proven to be the optimal, so the answer is $1$.

In the second test case, the array is $[2, 3, 4, 5, 6, 7, 8]$. Currently, the bitwise AND is $0$. However, after deleting $4$, $5$, and $8$, the array becomes $[2, 3, 6, 7]$, and the bitwise AND becomes $2$. This can be proven to be the optimal, so the answer is $3$. Note that there may be other ways to delete $3$ elements.

Source: codeforces | Difficulty: EASY
Tags: Bit manipulation

Mathematics

Greedy algorithms


Solutions:
def fun(n):
	n += 1
	i = 2
	arr = [0 for i in range(32)]
	j = 32
	while n >= i // 2:
		j -= 1
		x = n // i * (i // 2)
		if n % i > i // 2:
			x += n % i - i // 2
		arr[j] = x
		i = i * 2
	return arr
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	a = fun(r)
	b = fun(l - 1)
	for i in range(32):
		a[i] -= b[i]
	print(r + 1 - l - max(a))


from math import log2
for _ in range(int(input())):
	(least, large) = map(int, input().strip().split())
	leastbin = bin(least)[2:]
	best = 1
	b = int(log2(large))
	for i in range(b, -1, -1):
		power = 2 ** i
		firstone = int(leastbin[:len(leastbin) - i - 1] + '1' + '0' * i, 2)
		if least < power:
			firstone = power
		dif = large - firstone + 1
		if firstone > large:
			continue
		ans = dif // (power * 2) * power + min(power, dif % (power * 2))
		if firstone <= least:
			ans -= least - firstone
		best = max(best, ans)
	print(large - least - best + 1)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(l, r) = map(int, input().split())
	L1 = [0] * 18
	L2 = [0] * 18
	for i in range(18):
		(a, b) = divmod(l, 2 ** (i + 1))
		L1[i] = a * 2 ** i + max(0, b - 2 ** i)
	for i in range(18):
		(a, b) = divmod(r + 1, 2 ** (i + 1))
		L2[i] = a * 2 ** i + max(0, b - 2 ** i)
	m = 1000000
	for i in range(18):
		k = r - l + 1 - (L2[i] - L1[i])
		if k < m:
			m = k
	print(m)


def getcount(n, k):
	res = n >> k + 1 << k
	if n >> k & 1:
		res += n & (1 << k) - 1
	return res
for _ in range(int(input())):
	(l, r) = list(map(int, input().split()))
	n = r - l + 1
	if l == 1:
		m = 0
		for i in range(0, 32):
			m = max(m, getcount(r + 1, i))
		print(n - m)
		continue
	bits = [0] * 32
	for i in range(0, 32):
		bits[i - 1] = getcount(r + 1, i) - getcount(l, i)
	print(n - max(bits))


def find(l, r):
	if l == r:
		return 0
	big = 0
	while 2 ** big <= r:
		big += 1
	if 2 ** big <= l:
		return 0
	biggest = 0
	for i in range(big):
		gap = 2 ** (i + 1)
		q1 = int(l / gap)
		x1 = l % gap
		y1 = int(max(0, x1 - gap / 2))
		z1 = int(gap / 2 * q1 + y1)
		q2 = int((r + 1) / gap)
		x2 = (r + 1) % gap
		y2 = int(max(0, x2 - gap / 2))
		z2 = int(gap / 2 * q2 + y2)
		biggest = max(biggest, z2 - z1)
	return r - l + 1 - biggest
cases = int(input())
for _ in range(cases):
	line = input().split()
	l = int(line[0])
	r = int(line[1])
	print(find(l, r))


def calc_set_bits(n):
	array = []
	for i in range(1, 23, 1):
		if i == 1:
			tmp = n % 2
		else:
			tmp = n % 2 ** i - 2 ** (i - 1) + 1
			if tmp < 0:
				tmp = 0
		temp = 2 ** (i - 1) * (n // 2 ** i)
		array.append(temp + tmp)
	return array
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	set_bits_for_b = calc_set_bits(b)
	set_bits_for_a = calc_set_bits(a - 1)
	max_val = 0
	for i in range(len(set_bits_for_b)):
		max_val = max(max_val, set_bits_for_b[i] - set_bits_for_a[i])
	print(b - a + 1 - max_val)


def calOnes(n, k):
	res = n >> k + 1 << k
	if n >> k & 1:
		res += n & (1 << k) - 1
	return res
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	maxOnes = 0
	for j in range(32):
		maxOnes = max(calOnes(r + 1, j) - calOnes(l, j), maxOnes)
	print(r - l + 1 - maxOnes)


def fun(x, n):
	p = [0] * n
	for i in range(1, n + 1):
		p[i - 1] = x // a[i] * a[i - 1] + max(0, x % a[i] - a[i - 1])
	return p
t = int(input())
a = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144]
n = len(a) - 1
for _ in range(t):
	(l, r) = map(int, input().split())
	x = fun(r + 1, n)
	y = fun(l, n)
	for i in range(n):
		x[i] -= y[i]
	print(r - l + 1 - max(x))


def nonZero(arr):
	l = len(bin(arr[1])) - 2
	bit_count = [0] * l
	for i in range(l):
		zero = 0
		r = (arr[1] - arr[0]) // 2 ** (i + 1)
		zero += r * 2 ** i
		idx1 = arr[0] % 2 ** (i + 1)
		val1 = idx1 // 2 ** i
		idx2 = arr[1] % 2 ** (i + 1)
		val2 = idx2 // 2 ** i
		if val1 == 0 and val2 == 1:
			zero += 2 ** i - idx1
		elif val2 == 0 and val1 == 1:
			zero += idx2 + 1
		elif val2 == val1:
			if val2 == 1:
				if arr[1] - arr[0] > 2 ** i and idx2 < idx1:
					zero += 2 ** i
			elif arr[1] - arr[0] > 2 ** i:
				zero += 2 ** i - idx1 + idx2 + 1
			else:
				zero += arr[1] - arr[0] + 1
		bit_count[i] = zero
	return min(bit_count)
r = int(input())
res = []
for i in range(r):
	arr = list(map(int, input().split()))
	res.append(nonZero(arr))
for i in res:
	print(i)


arr = []
length = len(bin(200001).replace('0b', ''))
arr.append([0] * length)
for i in range(1, 200001):
	x = bin(i).replace('0b', '')
	x = '0' * (length - len(x)) + x
	m = arr[i - 1].copy()
	for j in range(len(x)):
		if x[j] == '0':
			m[j] += 1
	arr.append(m)
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	x = arr[l - 1]
	y = arr[r]
	z = []
	mini = 1000000000
	for i in range(len(x)):
		mini = min(y[i] - x[i], mini)
	print(mini)


import math

def getcount(n, k):
	res = n >> k + 1 << k
	if n >> k & 1:
		res += n & (1 << k) - 1
	return res
t = int(input())
for _ in range(t):
	(l, r) = list(map(int, input().split()))
	k = int(math.log(l, 2))
	print(min(r - l + 1 - getcount(r + 1, k) + getcount(l, k), r - l + 1 - getcount(r + 1, k + 1) + getcount(l, k + 1)))


def count_ones(elems, cycle_len):
	ret = elems // cycle_len * cycle_len // 2
	left = elems % cycle_len
	if left > cycle_len // 2:
		ret += left - cycle_len // 2
	return ret

def solve():
	(l, r) = [int(x) for x in input().split()]
	ret = 0
	cycle_len = 2
	for _ in range(20):
		ones = count_ones(r + 1, cycle_len) - count_ones(l, cycle_len)
		ret = max(ret, ones)
		cycle_len *= 2
	return r - l + 1 - ret
t = int(input())
for _ in range(t):
	print(solve())


z = [1]
for i in range(30):
	z.append(z[-1] * 2)
for i in range(int(input())):
	(l, r) = list(map(int, input().split()))
	x = r // 2 - (l - 1) // 2
	for i in range(31):
		cr = r // (2 * z[i]) * z[i]
		if r % (2 * z[i]) >= z[i]:
			cr += r % (2 * z[i]) - z[i] + 1
		cl = (l - 1) // (2 * z[i]) * z[i]
		if (l - 1) % (2 * z[i]) >= z[i]:
			cl += (l - 1) % (2 * z[i]) - z[i] + 1
		x = min(x, r - l + 1 - cr + cl)
	print(x)


import math
problem_num = int(input())
for problem in range(problem_num):
	arr = list(map(int, input().split()))
	(low, high) = arr
	num_0_lst = []
	num_1_lst = []
	ran = int(math.log2(high))
	for i in range(0, ran + 1):
		x = high // 2 ** (i + 1) * 2 ** (i + 1) - 1
		y = low // 2 ** (i + 1) * 2 ** (i + 1)
		length = x - y + 1
		count_0 = length // 2
		count_1 = length // 2
		count_to_high = high - x
		count_to_low = low - y
		if count_to_high // 2 ** i >= 1:
			count_0 += 2 ** i
			count_1 += count_to_high % 2 ** i
		else:
			count_0 += count_to_high
		if count_to_low // 2 ** i >= 1:
			count_0 -= 2 ** i
			count_1 -= count_to_low % 2 ** i
		else:
			count_0 -= count_to_low
		num_0_lst.append(count_0)
		num_1_lst.append(count_1)
	print(min(num_0_lst))


from collections import defaultdict

def mid(a, b):
	return (b - a + 1) // 2

def met1(a, b, p):
	if a > b:
		return 0
	if a // 2 ** p == b // 2 ** p:
		return b - a + 1 if b % 2 ** (p + 1) >= 2 ** p else 0
	elif b % 2 ** (p + 1) >= 2 ** p:
		return b - (next_smaller(b, p + 1) + 2 ** p) + 1
	else:
		return next_larger(a, p + 1) - a

def met2(a, b, p):
	return met1(a, next_larger(a, p + 1) - 1, p) + mid(next_larger(a, p + 1), next_smaller(b, p + 1) - 1) + met1(next_smaller(b, p + 1), b, p)

def next_smaller(a, p):
	return a // 2 ** p * 2 ** p

def next_larger(a, p):
	return (a // 2 ** p + 1) * 2 ** p

def bit_sets(a, b, p):
	if a % 2 ** (p + 1) == 0 and b % 2 ** (p + 1) == 2 ** (p + 1) - 1:
		return mid(a, b)
	if a // 2 ** (p + 1) == b // 2 ** (p + 1):
		return met1(a, b, p)
	else:
		return met2(a, b, p)
d = defaultdict(int)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	if (l, r) in d:
		print(d[l, r])
		continue
	(res, ln, mx) = (float('inf'), r - l + 1, len(bin(r)))
	for set_bit in range(mx - 1):
		cur = bit_sets(l, r, set_bit)
		res = min(res, ln - cur)
	print(res)
	d[l, r] = res


from collections import defaultdict as dd
import math
import sys
input = sys.stdin.readline

def nn():
	return int(input())

def li():
	return list(input())

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

def lm():
	return list(map(int, input().split()))
twos = [2 ** i for i in range(100)]

def solve():
	(l, r) = lm()
	pows = 20
	l_counts = [0 for i in range(pows)]
	r_counts = [0 for i in range(pows)]
	for i in range(1, pows):
		l_counts[i] = l // 2 ** i * 2 ** (i - 1) + max(0, l % 2 ** i - 2 ** (i - 1))
	for i in range(1, pows):
		r_counts[i] = (r + 1) // 2 ** i * 2 ** (i - 1) + max(0, (r + 1) % 2 ** i - 2 ** (i - 1))
	f_counts = [r_counts[i] - l_counts[i] for i in range(0, pows)]
	print(r - l + 1 - max(f_counts))
q = nn()
for _ in range(q):
	solve()


def func(a, b):
	bin_a = bin(a)[2:]
	bin_b = bin(b)[2:]
	max_len = len(bin_b)
	res1 = []
	b += 1
	for x in range(max_len):
		base = 2 ** (x + 1)
		num = a // base * (base // 2) + max(a % base - base // 2, 0)
		res1.append(num)
	res2 = []
	for x in range(max_len):
		base = 2 ** (x + 1)
		num = b // base * (base // 2) + max(b % base - base // 2, 0)
		res2.append(num)
	final = [x2 - x1 for (x1, x2) in zip(res1, res2)]
	max_num = max(final)
	print(b - a - max_num)
t = int(input())
while t > 0:
	t -= 1
	(m, n) = map(int, input().split())
	func(m, n)


import sys
t = int(sys.stdin.readline())
s = [i ** 2 for i in range(0, 20)]
for _ in range(t):
	(l, r) = map(int, sys.stdin.readline().split())
	maxR = 0
	m = [0] * 22
	for i in range(1, 22):
		x = (r + 1) // 2 ** i
		x1 = l // 2 ** i
		ost1 = max(0, (r + 1) % 2 ** i - 2 ** i // 2)
		ost2 = max(0, l % 2 ** i - 2 ** i // 2)
		m[i] = (x - x1) * 2 ** i // 2 + ost1 - ost2
	print(r - l + 1 - max(m))


import math
t = int(input())
for test in range(t):
	v = input().split(' ')
	l = int(v[0])
	r = int(v[1])
	x1 = bin(l - 1)
	x2 = bin(r)
	x1 = x1[2:]
	x2 = x2[2:]
	best = r - l
	for i in range(max(len(x1), len(x2))):
		v = (l - 1) // 2 ** (i + 1)
		rem = (l - 1) % 2 ** (i + 1)
		z = v * 2 ** i
		if rem < 2 ** i:
			z += rem + 1
		else:
			z += 2 ** i
		v1 = r // 2 ** (i + 1)
		rem = r % 2 ** (i + 1)
		z1 = v1 * 2 ** i
		if rem < 2 ** i:
			z1 += rem + 1
		else:
			z1 += 2 ** i
		if z1 - z >= 0:
			best = min(best, z1 - z)
	print(best)


def solve(tg, b):
	na = b % (tg * 2)
	mok = b - na
	return mok // 2 + na // tg * (na % tg + 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	tg = 1
	ans = 0
	while tg <= b:
		ans = max(ans, solve(tg, b) - solve(tg, a - 1))
		tg *= 2
	print(b - a + 1 - ans)


import os, sys
isCoding = os.environ.get('CODE_ENV', '') != ''
if isCoding:
	sys.stdin = open('./examples/1.in', 'r')
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	n = len(bin(r)) - 2
	d = r - l + 1
	a = [0] * 20
	a[0] += d // 2 + d % 2 * l % 2
	i = 1
	while i < 20:
		t = 2 ** i
		zl = l // t
		if zl % 2 == 0:
			zl += 1
		else:
			a[i] += min(r + 1, (zl + 1) * t) - l
			zl += 2
		zr = r // t
		if zr % 2 == 0:
			zr -= 1
		if zl <= zr:
			a[i] += t * ((zr - zl) // 2)
			zl = zr
			a[i] += min(r + 1, (zl + 1) * t) - zl * t
		i += 1
	a = [d - x for x in a]
	print(min(a))


import sys
input = sys.stdin.readline
max_n = 2 * 10 ** 5
num_digits = len(bin(max_n)) - 2
cumulative_one_counts = [[0 for i in range(num_digits)]]
for n in range(1, max_n + 1):
	cumulative_one_counts += [cumulative_one_counts[-1].copy()]
	binary = bin(n)
	for j in range(len(binary) - 2):
		if binary[~j] == '1':
			cumulative_one_counts[-1][~j] += 1
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	(left, right) = [int(x) for x in input().split()]
	max_num_ones = max((a - b for (a, b) in zip(cumulative_one_counts[right], cumulative_one_counts[left - 1])))
	ans = right - left + 1 - max_num_ones
	print(ans)


t = int(input())

def getcount(n, k):
	res = n >> k + 1 << k
	if n >> k & 1:
		res += n & (1 << k) - 1
	return res
for _ in range(t):
	(l, r) = list(map(int, input().strip().split()))
	n = r - l + 1
	arr = [n] * 32
	for k in range(32):
		arr[k] -= getcount(r + 1, k) - getcount(l, k)
	print(min(arr))


import sys

def readnum():
	input = sys.stdin.readline
	a = list(map(int, input().split()))
	return a

def printf(val):
	sys.stdout.write(str(val) + '\n')

def power(a, b, mod):
	if b == 1:
		return a
	if b == 0:
		return 1
	ans = power(a, b // 2, mod)
	ans *= ans
	if b % 2:
		ans *= a
	ans = ans % mod
	return ans

def factorial(n, start=1, skip=None):
	res = start
	for i in range(1, n + 1):
		if i == skip:
			continue
		res *= i
	return res

def make_deg(l):
	deg = {}
	for i in l:
		if not i in deg:
			deg[i] = 0
		deg[i] += 1
	return deg

def get_num_of_bits(n):
	res = []
	for i in range(1, 31):
		res.append(2 ** (i - 1) * (n // 2 ** i) + max(0, n % 2 ** i - 2 ** (i - 1)))
	return res

def minus(l, r):
	res = []
	for i in range(len(l)):
		res.append(r[i] - l[i])
	return res
for _ in range(readnum()[0]):
	(l, r) = readnum()
	res = minus(get_num_of_bits(l), get_num_of_bits(r + 1))
	print(r - l - max(res) + 1)


from collections import Counter
from queue import Queue
import math

def func2(m, n):
	if m < 1 << n:
		return 0
	if m == 1 << n:
		return 1
	if m & 1 << n != 0:
		k = (m | (1 << n) - 1) - ((1 << n) - 1)
		if k == 1 << n:
			return m - k + 1
		else:
			M = m - k + 1 + (k - (1 << n)) // 2
			return M
	else:
		for k in range(n + 1, m):
			if m & 1 << k != 0:
				kk = (m | (1 << k) - 1) - (1 << k)
				if kk >= m:
					raise Exception
				return func2(kk, n)
T = int(input())
for t in range(T):
	(l, r) = [int(a) for a in input().split()]
	ans = r
	for n in range(r):
		if 1 << n > r:
			break
		(ll, rr) = (func2(l - 1, n), func2(r, n))
		ans = min(ans, r - l + 1 - (rr - ll))
	print(ans)


for _ in [*open(0)][1:]:
	(l, r) = map(int, _.split())
	k = len(bin(r)) - 2
	print(min((r // 2 ** i * 2 ** (i - 1) + min(2 ** (i - 1) - 1, r % 2 ** i) - (l - 1) // 2 ** i * 2 ** (i - 1) - min(2 ** (i - 1) - 1, (l - 1) % 2 ** i) for i in range(1, k + 1))))


read = lambda : map(int, input().split())

def f(x, bit):
	y = x >> bit
	res = y // 2 << bit
	if y & 1:
		res += x - (y << bit) + 1
	return res
t = int(input())
for _ in range(t):
	(l, r) = read()
	res = r - l + 1
	for bit in range(21):
		cur = f(r, bit) - f(l - 1, bit)
		cur = r - l + 1 - cur
		if cur < res:
			res = cur
	print(res)


def c0(n, len):
	cnt = n // len
	return cnt * (len // 2) + min(n - cnt * len, len // 2)

def solve():
	(l, r) = [int(x) for x in input().split()]
	mz = r + 1
	for bit in range(19):
		len = 2 ** (bit + 1)
		z = c0(r + 1, len)
		if l > 0:
			z -= c0(l, len)
		mz = min(mz, z)
	print(mz)
for i in range(int(input())):
	solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter, defaultdict
import math

def nck(n, k):
	res = 1
	for i in range(1, k + 1):
		res = res * (n - i + 1) // i
	return res
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	ans = 10 ** 9
	arr = [0] * 32
	for j in range(32):
		pos = (r + 1) // 2 ** j
		end = 2 ** j * (pos // 2)
		if pos % 2:
			end += (r + 1) % 2 ** j
		pos = l // 2 ** j
		start = 2 ** j * (pos // 2)
		if pos % 2:
			start += l % 2 ** j
		arr[j] = end - start
	for j in range(32):
		ans = min(ans, r - l + 1 - arr[j])
	print(ans)


import math
import random
T = int(input())
for t in range(T):
	arrayz = [int(i) for i in input().split()]
	l = min(arrayz)
	r = max(arrayz)
	d = dict()
	s = 1
	dig = []
	for i in range(30):
		dig.append(s)
		s *= 2
	mul = 2
	for i in range(len(dig)):
		start = dig[i]
		if start > r:
			break
		m1 = (l - start) / mul
		m1 = math.ceil(m1)
		first = m1 * mul + start
		if first <= r:
			sets = (r - first + 1) // mul
			tot = sets * mul / 2
			nw = first + mul * sets
			tot += max(min(r - nw + 1, mul / 2), 0)
			gap = first - l
			gap -= mul / 2
			tot += max(0, gap)
			d[i] = tot
		else:
			prev = first - mul
			tot = min(r + 1, prev + mul / 2) - max(prev, l)
			d[i] = tot
		mul *= 2
	m = 0
	for i in d:
		m = max(m, d[i])
	ans1 = int(r - l + 1 - m)
	print(ans1)
	p = 'd=dict()\n    for i in range(l,r+1):\n        s=bin(i)[2:]\n        s=s[::-1]\n        for i in range(len(s)):\n            if s[i] ==\'1\':\n                if i in d:\n                    d[i]+=1\n                else:\n                    d[i]=1\n    m=0\n    for i in d:\n        m=max(m,d[i])\n    ans2=(r-l+1-m)\n    if ans1!=ans2:\n        print("error",ans1,ans2,l,r)\n    else:\n        pass'


lis = []
k = 25
mp = {}
for i in range(2 * 10 ** 5 + 3):
	s = bin(i)[2:][::-1]
	s += '0' * (k - len(s))
	for i in range(len(s)):
		if i not in mp:
			mp[i] = 0
		if s[i] == '0':
			mp[i] += 1
	lis.append(mp.copy())
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	ans = 2 ** 31
	for i in range(k):
		ans = min(ans, lis[r][i] - lis[l - 1][i])
	print(ans)


dp = [[0] * 19 for i in range(200001)]
for i in range(1, 200001):
	t = bin(i)[2:]
	n = len(t)
	for j in range(-1, -n - 1, -1):
		if t[j] == '1':
			dp[i][j] = dp[i - 1][j] + 1
		else:
			dp[i][j] = dp[i - 1][j]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	t = 0
	for i in range(19):
		t = max(t, dp[r][i] - dp[l - 1][i])
	ans = r - l + 1 - t
	print(ans)


t = int(input())
for _ in range(t):
	(l, r) = input().split(' ')
	l = int(l)
	r = int(r)
	length = r - l + 1
	l -= 1
	i = 2
	ans = 0
	while r * 2 // i != 0:
		temp1 = l // i * i / 2
		if l * 2 // i == 0:
			temp1 = 0
		if int(temp1) != temp1:
			temp1 = int(temp1 + 0.5)
		temp2 = r // i * i / 2
		if int(temp2) != temp2:
			temp2 = int(temp2 + 0.5)
		if r % i != 0 and r * 2 >= i:
			temp = r - (r // i * i + i / 2) + 1
			if temp > 0:
				temp2 += temp
		if l % i != 0 and l * 2 >= i:
			temp = l - (l // i * i + i / 2) + 1
			if temp > 0:
				temp1 += temp
		tep = temp2 - temp1
		if tep > ans:
			ans = tep
		i = i * 2
	print(int(length - ans))


import sys

def and_its_non_zero(l, r):
	counts_l = count_ones(l - 1)
	counts_r = count_ones(r)
	max_ones = 0
	for pos in counts_r:
		max_ones = max(max_ones, counts_r[pos] - counts_l.get(pos, 0))
	return r - l + 1 - max_ones

def count_ones(up_to):
	if up_to == 0:
		return {0: 0}
	i = 1
	while True:
		if up_to < 2 ** i:
			break
		i += 1
	i -= 1
	counts = {i: 1}
	for j in range(i):
		counts[j] = 2 ** (i - 1)
	up_to -= 2 ** i
	counts[i] += up_to
	for (pos, count) in count_ones(up_to).items():
		counts[pos] += count
	return counts
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	sys.stdout.write(f'{and_its_non_zero(l, r)}\n')


def h(n, k):
	return max(0, n - (1 << k) + 1)

def g(l, r, k):
	res_l = l & (1 << k + 1) - 1
	res_r = r & (1 << k + 1) - 1
	q_l = l >> k + 1
	q_r = r >> k + 1
	val = (q_r - q_l) * (1 << k)
	val += h(res_r, k)
	val -= h(res_l, k)
	if l & 1 << k:
		val += 1
	return val

def f(l, r):
	score = 0
	for k in range(20):
		score = max(score, g(l, r, k))
	return r - l + 1 - score
t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	print(f(l, r))


import sys
import bisect
inp = sys.stdin.readline

def print(s):
	sys.stdout.write('{}\n'.format(s))

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

def lcm(a, b):
	return a * b // gcd(a, b)
a = [[0] * 20 for i in range(200005)]
for i in range(1, 200005):
	for (idx, j) in enumerate(bin(i)[2:][::-1]):
		a[i][idx] = a[i - 1][idx] + (j == '1')
for _ in range(int(inp())):
	(l, r) = map(int, inp().split())
	t = 0
	for i in range(20):
		t = max(t, a[r][i] - a[l - 1][i])
	print(r - l + 1 - t)


n = 2 * 10 ** 5 + 1
k = 18
dp = [[0 for i in range(n + 1)] for j in range(18)]
for i in range(k):
	for j in range(1, n + 1):
		if j & 1 << i:
			dp[i][j] = dp[i][j - 1] + 1
		else:
			dp[i][j] = dp[i][j - 1]

def func():
	(l, r) = map(int, input().split())
	req = -1
	for i in range(k):
		req = max(req, dp[i][r] - dp[i][l - 1])
	return r - l + 1 - req
t = int(input())
for i in range(t):
	print(func())


import math

def main_function():
	test_cases = range(int(input()))
	for test_case in test_cases:
		(l, r) = [int(i) for i in input().split(' ')]
		l = max(0, l - 1)
		collector = []
		s = 2
		x = 0
		while True:
			if s ** x <= r:
				collector.append(x)
			else:
				break
			x += 1
		min_val = 1000000000000000000000000000
		for i in range(len(collector)):
			period = 2 ** (collector[i] + 1)
			starting_period = 2 ** collector[i] - 1
			target = 2 ** collector[i]
			new_l = l - starting_period
			new_r = r - starting_period
			if new_r <= 0:
				new_r = 0
			if new_l <= 0:
				new_l = 0
			remainder_r = new_r % period
			counter_period = new_r // period
			real_r_counter = counter_period * target
			real_r_counter += min(remainder_r, target)
			remainder_l = new_l % period
			counter_period_l = new_l // period
			real_l_counter = counter_period_l * target
			real_l_counter += min(remainder_l, target)
			total_counter_m = r - l - (real_r_counter - real_l_counter)
			if total_counter_m < min_val:
				min_val = total_counter_m
		print(min_val)
main_function()


lm = {}
q = [0] * 18
for i in range(10 ** 5 * 2 + 1):
	s = bin(i)[2:][::-1]
	s += '0' * (18 - len(s))
	for j in range(len(s)):
		if s[j] == '0':
			q[j] += 1
	lm[i] = q.copy()
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	m = 2 ** 31
	for (i, j) in zip(lm[a - 1], lm[b]):
		m = min(m, j - i)
	print(m)


from sys import stdin
input = stdin.readline

def bitcount(n, bit, mbit):
	istheir = False
	ans = 0
	for i in range(mbit, -1, -1):
		if not istheir and i < bit:
			break
		if n >> i & 1:
			if i > bit:
				ans += 1 << i - 1
			elif i < bit:
				ans += 1 << i
			else:
				istheir = True
				ans += 1
	return ans

def answer():
	ans = float('inf')
	total = r - l + 1
	for i in range(30):
		x = bitcount(r, i, 30) - bitcount(l - 1, i, 30)
		ans = min(ans, total - x)
	return ans
for T in range(int(input())):
	(l, r) = map(int, input().split())
	print(answer())


for _ in range(int(input())):
	(l, r) = map(int, input().split())
	m = float('inf')
	two = 2
	while two // 2 <= r:
		lp = two * (l // two)
		rp = two * (r // two)
		mm = (rp - lp) // 2
		mm -= min(two // 2, l - lp)
		mm += min(two // 2, r - rp + 1)
		m = min(m, mm)
		two *= 2
	print(m)


import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
prin = sys.stdout.write
(t,) = I()
for _ in range(t):
	(l, r) = I()
	best = 0
	size = r - l + 1
	i = 1
	while i < 3 * 10 ** 5:
		tot = i * (size // (2 * i))
		a = (l - 1) % (2 * i)
		b = r % (2 * i)
		if b > a:
			tot += max(0, b - max(i - 1, a))
		elif b < a:
			tot += min(i, 2 * i - a - 1)
			tot += max(0, b - i)
		if tot > best:
			best = tot
		i *= 2
	print(size - best)


def gv(x, y):
	if x < 1:
		return 0
	if y == 1:
		return (x + 1) // 2
	cnt = x // (2 * y) * y
	x %= 2 * y
	if x >= y:
		return cnt + x - y + 1
	return cnt
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	if l == r:
		print(0)
		continue
	mxc = 0
	for i in range(23):
		cnt = gv(r, 2 ** i) - gv(l - 1, 2 ** i)
		mxc = max(mxc, cnt)
	print(r - l + 1 - mxc)


def calc(n):
	array = [0 for i in range(19)]
	for i in range(19):
		array[i] = n // 2 ** (i + 1) * 2 ** i
		temp = n % 2 ** (i + 1) + 1
		if temp <= 2 ** i:
			array[i] += temp
		else:
			array[i] += 2 ** i
	return array
for t in range(int(input())):
	(l, r) = [int(i) for i in input().split()]
	l1 = calc(r)
	l2 = calc(l - 1)
	final = []
	for i in range(19):
		final.append(l1[i] - l2[i])
	print(min(final))


def andItsNonZero(l, r):
	a = len(bin(r)[2:])
	m = float('inf')
	for i in range(a):
		x = 2 ** i * ((r + 1) // 2 ** (i + 1)) + min((r + 1) % 2 ** (i + 1), 2 ** i)
		y = 2 ** i * (l // 2 ** (i + 1)) + min(l % 2 ** (i + 1), 2 ** i)
		if x - y < m:
			m = x - y
	return m
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	print(andItsNonZero(l, r))


import sys, math
bit_count = [0] * 32
input = sys.stdin.readline

def find(n):
	count = 0
	while n >= 1:
		n //= 2
		count += 1
	return count

def solve(l, r):
	for i in range(l, r + 1):
		bit(i)
	return max(bit_count)

def bit(a):
	temp = a
	n = 0
	while temp > 0:
		bit_count[n] += temp % 2
		temp = temp // 2
		n += 1

def bit_make():
	bit_map = [[0 for _ in range(200001)] for _ in range(18)]
	for i in range(18):
		for j in range(1, 200001):
			bit_map[i][j] = bit_map[i][j - 1] + (1 if j & 1 << i else 0)
	return bit_map
t = int(input())
bit_map = bit_make()
for _ in range(t):
	(l, r) = map(int, input().split(' '))
	b = [bit_map[j][r] - bit_map[j][l - 1] for j in range(18)]
	answer = max(b)
	print(r - l + 1 - answer)


import math

def count(n, i):
	return (n + 1) // 2 ** (i + 1) * 2 ** i + max(0, (n + 1) % 2 ** (i + 1) - 2 ** i)

def solve(l, r):
	ans = 0
	m = int(math.log(r, 2))
	for i in range(m + 1):
		ans = max(ans, count(r, i) - count(l - 1, i))
	print(r - l + 1 - ans)
t = int(input())
while t > 0:
	arr = [int(k) for k in input().split()]
	(l, r) = arr
	solve(l, r)
	t -= 1


import sys
input = sys.stdin.readline
for i in ' ' * int(input()):
	(l, r) = map(int, input().split())
	mx = 0
	c = 1
	while c <= r:
		k1 = (l - 1) // (2 * c) * c + max(0, (l - 1) % (2 * c) - (c - 1))
		k2 = r // (2 * c) * c + max(0, r % (2 * c) - (c - 1))
		mx = max(k2 - k1, mx)
		c *= 2
	print(r - l + 1 - mx)


a = []
c = 1
for rr in range(1, 20):
	a1 = [0] * (2 * 10 ** 5 + 1)
	b = 0
	for r in range(1, 2 * 10 ** 5 + 1):
		if r & c != 0:
			b += 1
		a1[r] += b
	c *= 2
	a.append(a1)
t = int(input())
for ttt in range(t):
	(x, y) = map(int, input().split())
	m = -1 * 10 ** 6
	for u in range(0, 19):
		mm = a[u][y] - a[u][x - 1]
		m = max(mm, m)
	print(y - x + 1 - m)


t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	r += 1
	m = 99999999999
	for j in range(25):
		a = l // 2 ** (j + 1) * 2 ** j + min(l % 2 ** (j + 1), 2 ** j)
		b = r // 2 ** (j + 1) * 2 ** j + min(r % 2 ** (j + 1), 2 ** j)
		m = min(b - a, m)
	print(m)


def solve():
	(l, r) = map(int, input().split())
	po = 1
	mzcnt = 100000000000
	while po <= r:
		po *= 2
		rzcnt = (r - r % po) // 2 + min(r % po + 1, po // 2)
		lzcnt = (l - 1 - (l - 1) % po) // 2 + min((l - 1) % po + 1, po // 2)
		mzcnt = min(mzcnt, rzcnt - lzcnt)
	print(mzcnt)
for _ in range(int(input())):
	solve()


import bisect
import collections
import math
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

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

def lli(rows):
	return [li() for _ in range(rows)]

def si():
	return input()

def ii():
	return int(input())

def ins():
	return input().split()

def drank(d, processing, da, rank):
	tmp = 10 ** 9
	if len(d[da]) == 1:
		return 1
	for di in d[da]:
		if processing[di - 1] == 0:
			processing[di - 1] = 1
			tmp = min(tmp, drank(d, processing, di, rank))
			processing[di - 1] = 0
	rank[da - 1] = tmp + 1
	return tmp + 1

def binary_search(n, a):
	l = len(a)
	low = 0
	high = l - 1
	while high >= low:
		mid = (high + low) // 2
		if a[mid] == n:
			return mid
		elif a[mid] > n:
			high = mid - 1
		else:
			low = mid + 1
	return -1
is_prime = [True] * (10 ** 6 + 1)

def primeseive(n):
	is_prime[0] = is_prime[1] = False
	i = 2
	while i * i <= n:
		if is_prime[i] == True:
			for j in range(i * i, n + 1, i):
				is_prime[j] = False
		i += 1

def solve():
	(l, r) = li()
	if l == r:
		return 0
	p = 1
	ans = 0
	while True:
		x = 2 ** p
		max_ones = (r + 1) // x * (x // 2) + max((r + 1) % x - x // 2, 0)
		min_ones = l // x * (x // 2) + max(l % x - x // 2, 0)
		ans = max(ans, max_ones - min_ones)
		if x > r:
			break
		p += 1
	return r - l + 1 - ans

def main():
	for _ in range(ii()):
		sys.stdout.write(str(solve()) + '\n')
main()


d = {}
l = [0 for i in range(18)]
for i in range(2 * 10 ** 5 + 1):
	bi = bin(i)[2:].zfill(18)
	for x in range(18):
		if bi[x] == '0':
			l[x] += 1
	d[i] = (*(num for num in l),)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(min((dr - dl for (dl, dr) in zip(d[l - 1], d[r]))))


import sys
input = sys.stdin.readline
from collections import defaultdict

def numberOfOnes(n):
	count = defaultdict(int)
	i = 2
	while i <= n * 2:
		count[i // 2] = (n + 1) // i * i // 2 + max(0, (n + 1) % i - i // 2)
		i *= 2
	return count
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	count1 = numberOfOnes(l - 1)
	count2 = numberOfOnes(r)
	for key in count2.keys():
		count2[key] -= count1[key]
	print(r - l + 1 - max(count2.values()))


from math import ceil, log2, floor, sqrt, gcd
from collections import defaultdict, deque
from bisect import bisect_left
import sys
import os.path
from itertools import permutations
sys.setrecursionlimit(200000)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r+')
	sys.stdout = open('output.txt', 'w')

def MI():
	return map(int, input().split())
mod = 10 ** 9 + 7

def getcount(n, k):
	res = n >> k + 1 << k
	if n >> k & 1:
		res += n & (1 << k) - 1
		res += 1
	return res

def solve(testcase):
	(l1, r1) = MI()
	ans = 10 ** 9
	t = r1 - l1 + 1
	for i in range(33):
		a = getcount(r1, i)
		b = getcount(l1 - 1, i)
		ans = min(ans, t - (a - b))
	print(ans)
t = int(input())
for _ in range(t):
	solve(_ + 1)


t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	m = len(bin(r)[2:])
	ans = 200001
	for i in range(m):
		s = 0
		lc = l // 2 ** (i + 1)
		lr = l % 2 ** (i + 1)
		rc = r // 2 ** (i + 1)
		rr = r % 2 ** (i + 1)
		if lc < rc:
			s += (rc - lc - 1) * 2 ** i
		s += max(2 ** i - lr, 0)
		if lc < rc:
			s += min(rr + 1, 2 ** i)
		ans = min(s, ans)
	print(ans)


T = int(input())

def stupid(frm, to):
	bits = [0 for i in range(20)]
	for x in range(frm, to + 1):
		for bit in range(20):
			if x & 1 << bit == 0:
				bits[bit] += 1
	return bits

def solve(frm, to):
	best = to + frm + 1000
	res = []
	for bit in range(20):
		fromBlockPos = frm % (1 << bit)
		toBlockPos = to % (1 << bit)
		from1 = frm & 1 << bit > 0
		to1 = to & 1 << bit > 0
		zeroes = 0
		newFrom = frm - fromBlockPos
		newTo = to - toBlockPos - 1
		if not to1:
			zeroes += toBlockPos + 1
		if not from1:
			zeroes -= fromBlockPos
		blockSize = 1 << bit
		blockCount = (newTo - newFrom + 1) // blockSize
		zeroes += blockCount // 2 * blockSize
		if blockCount % 2 == 1 and (not from1):
			zeroes += blockSize
		res.append(zeroes)
	return res
for _ in range(T):
	(frm, to) = map(int, input().split())
	print(min(solve(frm, to)))


T = int(input())
for t in range(T):
	(l, r) = [int(i) for i in input().split()]
	diff = r - l + 1
	i = 0
	ans = diff
	while 1 << i <= r:
		at_r = r // (2 * (1 << i)) * (1 << i)
		modval = 0
		if i >= 0:
			modval = r % (2 * (1 << i))
		incr = 0
		if modval >= 1 << i:
			incr = modval - (1 << i) + 1
		total_at_r = at_r + incr
		at_l = (l - 1) // (2 * (1 << i)) * (1 << i)
		modval = 0
		if i >= 0:
			modval = (l - 1) % (2 * (1 << i))
		incr = 0
		if modval >= 1 << i:
			incr = modval - (1 << i) + 1
		total_at_l = at_l + incr
		ans = min(ans, diff - (total_at_r - total_at_l))
		i += 1
	print(ans)


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
stinput = lambda : stdin.readline()[:-1]
ii = lambda : int(stinput())
mi = lambda : map(int, stdin.readline().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, stdin.readline().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, stdin.readline().split())
lis = lambda : list(mis())
from collections import defaultdict
import heapq
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0

def f(n):
	cnt = [0] * 20
	for i in range(20):
		tmp = 0
		m = n // pow(2, i + 1)
		tmp += m * pow(2, i)
		k = m * pow(2, i + 1)
		tmp += max(n - k - pow(2, i) + 1, 0)
		cnt[i] = tmp
	return cnt
t = ii()
for _ in range(t):
	(l, r) = mi()
	n = r - l + 1
	ans = n
	a = f(r)
	b = f(l - 1)
	for i in range(20):
		ans = min(ans, n - (a[i] - b[i]))
	print(ans)


a = [[0 for _ in range(200001)] for _ in range(18)]
for j in range(18):
	for i in range(1, 200001):
		a[j][i] = a[j][i - 1] + (1 if i & 1 << j else 0)
t = int(input())
while t:
	(l, r) = [int(x) for x in input().split()]
	b = [a[j][r] - a[j][l - 1] for j in range(18)]
	print(r - l + 1 - max(b))
	t -= 1