Igor is in 11th grade. Tomorrow he will have to write an informatics test by the strictest teacher in the school, Pavel Denisovich.

Igor knows how the test will be conducted: first of all, the teacher will give each student two positive integers $a$ and $b$ ($a < b$). After that, the student can apply any of the following operations any number of times:

$a := a + 1$ (increase $a$ by $1$),

$b := b + 1$ (increase $b$ by $1$),

$a := a \ | \ b$ (replace $a$ with the bitwise OR of $a$ and $b$).

To get full marks on the test, the student has to tell the teacher the minimum required number of operations to make $a$ and $b$ equal.

Igor already knows which numbers the teacher will give him. Help him figure out what is the minimum number of operations needed to make $a$ equal to $b$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The only line for each test case contains two integers $a$ and $b$ ($1 \le a < b \le 10^6$).

It is guaranteed that the sum of $b$ over all test cases does not exceed $10^6$.


-----Output-----

For each test case print one integer — the minimum required number of operations to make $a$ and $b$ equal.


-----Examples-----

Input
5
1 3
5 8
2 5
3 19
56678 164422
Output
1
3
2
1
23329


-----Note-----

In the first test case, it is optimal to apply the third operation.

In the second test case, it is optimal to apply the first operation three times.

In the third test case, it is optimal to apply the second operation and then the third operation.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Sorting

Complete search

Dynamic programming

Mathematics


Solutions:
import sys, collections

def solve(a, b):
	sa = bin(a)[2:]
	sb = bin(b)[2:]
	sa = '0' * (len(sb) - len(sa)) + sa
	res = b - a
	found = False
	for i in range(len(sa)):
		state = sa[i] + sb[i]
		if state == '10':
			found = True
			sbb = sb[:i] + sa[i:]
			cur = int(sbb, 2) - b + 1
			res = min(res, cur)
			j = i
			while sa[j] == '1':
				j -= 1
			saa = sa[:j] + '1' + '0' * (len(sa) - j - 1)
			if sb[j] == '1':
				cur = int(saa, 2) - a
				if int(saa, 2) != b:
					cur += 1
				res = min(res, cur)
			else:
				sbb = sb[:j] + '1' + '0' * (len(sb) - j - 1)
				cur = int(saa, 2) - a + int(sbb, 2) - b
				if int(saa, 2) != int(sbb, 2):
					cur += 1
				res = min(res, cur)
			break
	return res if found else 1
input = sys.stdin.readline
tests = int(input()[:-1])
for test in range(tests):
	(a, b) = [int(s) for s in input()[:-1].split()]
	print(solve(a, b))


import math
t = int(input())
for i in range(t):
	(a, b) = [int(c) for c in input().split(' ')]
	A = b - a
	abin = '{0:b}'.format(a)
	bbin = '{0:b}'.format(b)
	abin = (len(bbin) - len(abin)) * '0' + abin
	j = 0
	while j < len(bbin) and bbin[j] >= abin[j]:
		j += 1
	v = j
	if v == len(bbin):
		print(1)
		continue
	if j < len(bbin):
		assert abin[v] == '1' and bbin[v] == '0'
	if j == len(bbin):
		j -= 1
	while bbin[j] <= abin[j]:
		j -= 1
	u = j
	B = 1 + int(abin[v:], 2) - int(bbin[v:], 2)
	j = 0
	C = 1 + 2 ** (len(bbin) - u - 1) - int(abin[u:], 2)
	print(min(A, B, C))


import math

def answer(a, b):
	if a == b:
		return 0
	if a | b == b:
		return 1
	d = math.floor(math.log((a | b) - b, 2))
	caseA = 2 ** d - (2 ** d - 1 & a)
	newa = a + caseA
	caseB = 2 ** d - (2 ** d - 1 & b)
	if newa | b == b:
		return min(caseA + answer(newa, b), caseB + answer(a, b + caseB))
	else:
		return caseB + answer(a, b + caseB)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	cnt = 0
	print(answer(a, b))


import sys
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
	(a, b) = map(int, input().split())
	ret = b - a
	tmp = a
	while tmp | b != b:
		tmp += 1
	ret = min(ret, 1 + tmp - a)
	tmp = b
	while a | tmp != tmp:
		tmp += 1
	ret = min(ret, 1 + tmp - b)
	print(ret)


t = int(input())

def steps(a, b):
	if a == b:
		print(0)
		return
	if b == b | a:
		print(1)
		return
	ans1 = b - a
	ans2 = 0
	for i in range(a, b):
		ans2 = ans2 + 1
		if i | b == b:
			break
	ans3 = (a | b) - b + 1
	ans4 = 0
	while True:
		b = b + 1
		ans4 += 1
		if a | b == b:
			break
	ans4 += 1
	print(min(ans1, ans2, ans3, ans4))
for _ in range(t):
	inp = list(map(int, input().split()))
	(a, b) = inp
	steps(a, b)


def check(a, b):
	mn = abs(a - b)
	tmp = a
	while tmp | b != b:
		tmp += 1
	mn = min(mn, 1 + tmp - a)
	tmp = b
	while a | tmp != tmp:
		tmp += 1
	mn = min(mn, 1 + tmp - b)
	return mn
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	print(check(a, b))


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	(a, b) = [int(char) for char in input().split()]
	if b == a:
		return 0
	ans = b - a
	(A, B) = (a, b)
	for i in range(b - a):
		if A + i | B == B:
			ans = min(ans, i + 1)
			break
	(A, B) = (a, b)
	for i in range(b - a):
		if B + i | A == B + i:
			ans = min(ans, i + 1)
			break
	return ans
for _ in range(int(input())):
	print(solve())


a = '001101110101100110'
b = '101000001001000110'
c = '101101111101100110'
ans = '101101100100001'

def main():
	(a, b) = map(int, input().split())
	k1 = 0
	(a1, b1) = (a, b)
	while a1 | b1 != b1:
		a1 += 1
		k1 += 1
	if a1 != b1:
		k1 += 1
	k2 = 0
	(a2, b2) = (a, b)
	while a2 | b2 != b2:
		b2 += 1
		k2 += 1
	if a2 != b2:
		k2 += 1
	print(min(k1, k2))
t = int(input())
for _ in range(t):
	main()


def answer(a, b):
	c = min(b - a, (b | a) - b + 1)
	k = 1
	m = a
	n = b
	k1 = 1
	while a | b > b:
		b += 1
		k += 1
	while m | n > n:
		m += 1
		k1 += 1
	return min(c, k1, k)
t = int(input())
for k in range(t):
	inp = input().split()
	a = int(inp[0])
	b = int(inp[1])
	print(answer(a, b))


t = int(input())

def solve(a, b):
	res = min(b - a, (b | a) - b + 1)
	(u, v) = (a, b)
	(tmp1, tmp2) = (0, 0)
	while b | a > b:
		b += 1
		tmp1 += 1
	while u | v > v:
		u += 1
		tmp2 += 1
	return min(res, tmp1 + 1, tmp2 + 1)
for _ in range(t):
	(a, b) = map(int, input().split())
	print(solve(a, b))


def s(a, b):
	(c, d) = (a, b)
	ans1 = ans2 = 1
	ans3 = b - a
	while a | b != b:
		a += 1
		ans1 += 1
	while c | d != d:
		d += 1
		ans2 += 1
	print(min(ans1, ans2, ans3))
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s(a, b)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = b - a
	for i in range(0, a + 1):
		if a + i | b == b:
			ans = min(ans, i + 1)
			break
	for i in range(b + 1):
		if b + i | a == b + i:
			ans = min(ans, i + 1)
			break
	print(ans)


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def solve():
	pass
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	ans1 = 1
	ans2 = 1
	A = a
	B = b
	while B != A | B:
		A += 1
		ans1 += 1
	A = a
	B = b
	while B != A | B:
		B += 1
		ans2 += 1
	print(min(ans1, ans2, b - a))


import bisect
import heapq
from collections import defaultdict, deque
from email import header
from functools import lru_cache
from sys import stdin, stdout
import math
import sys
input = stdin.readline

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

def lii():
	return list(map(int, stdin.readline().split()))

def ss():
	x = stdin.readline()
	if x[-1] == '\n':
		return x[:-1]
	return x

def lss():
	return list(map(str, stdin.readline().split()))

def llss():
	return [i for i in ss()]

def yes():
	stdout.write('YES\n')

def no():
	stdout.write('NO\n')
for _ in range(ii()):
	(a, b) = lii()
	(x, y) = (a, b)
	res = 0
	while x & y != x:
		x += 1
		res += 1
	if x != y:
		res += 1
	curr = 0
	(x, y) = (a, b)
	while x & y != x:
		y += 1
		curr += 1
	if x != y:
		curr += 1
	print(min(curr, res))


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	for i in range(a + b):
		if a + i | b == b or a | b + i == b + i:
			break
	print(min(i + 1, b - a))


n = int(input())
for _ in range(n):
	(a, b) = map(int, input().split())
	ans = b - a
	ans1 = 1
	ans2 = 1
	(c, d) = (a, b)
	while a | b != b:
		a += 1
		ans1 += 1
	while c | d != d:
		d += 1
		ans2 += 1
	print(min(ans2, ans1, ans))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a | b == b:
		print(1)
	else:
		n1 = b - a
		c = 1
		b1 = b
		while a | b != b:
			b = b + 1
			c = c + 1
		c1 = 1
		while a | b1 != b1:
			a = a + 1
			c1 = c1 + 1
		print(min(n1, c, c1))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	(q, w) = (a, b)
	k = 1
	r = 1
	o = min(b - a, (b | a) - b + 1)
	while a | b > b:
		b += 1
		k += 1
	while q | w > w:
		q += 1
		r += 1
	print(min(o, k, r))


t = int(input())
while t != 0:
	t = t - 1
	c = 0
	(a, b) = map(int, input().split())
	test = b
	d = 0
	ans1 = (a | b) - b + 1
	if a | b == b:
		print('1')
		continue
	ans2 = b - a
	for i in range(a, b):
		c = c + 1
		if i | b == b:
			break
	ans3 = c
	while True:
		test = test + 1
		d = d + 1
		if a | test == test:
			break
	ans4 = d + 1
	total = min(ans1, ans2, ans3, ans4)
	print(total)


t = int(input())
while t:
	(a, b) = list(map(int, input().split(' ')))
	count = b - a
	for i in range(b):
		if b == b | i:
			count = min(count, 1 + abs(i - a))
	print(count)
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = int(a)
	d = int(b)
	c1 = 0
	c2 = 0
	while a != b:
		if a | b == b:
			c1 += 1
			a = a | b
		else:
			a += 1
			c1 += 1
	while c != d:
		if c | d == d:
			c2 += 1
			c = c | d
		else:
			d += 1
			c2 += 1
	print(min(c1, c2))


for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	ans = b - a
	for i in range(b):
		if b == b | i:
			ans = min(ans, 1 + abs(i - a))
	print(ans)


t = int(input())
for i in range(t):
	q = input().split(' ')
	a = int(q[0])
	b = int(q[1])
	k1 = 0
	while a <= b:
		if b == a:
			break
		if b == a | b:
			k1 += 1
			break
		else:
			k1 += 1
			a += 1
	a = int(q[0])
	b = int(q[1])
	k2 = 0
	while True:
		if b == a | b:
			k2 += 1
			break
		else:
			k2 += 1
			b += 1
	print(min(k1, k2))


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	al = int(math.log2(a) // 1)
	bl = int(math.log2(b) // 1)
	a1 = a
	b1 = b
	d = b - a
	if b | a == b:
		print(1)
		continue
	else:
		c = 0
		for i in range(2 ** (bl - 1), 2 ** bl):
			c += 1
			a1 += 1
			b1 += 1
			if a1 | b == b:
				d = c + 1 if d > c + 1 else d
				break
			if b1 | a == b1:
				d = c + 1 if d > c + 1 else d
				break
	print(d)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	(c, d) = (x, y)
	a = 0
	b = 0
	while x != y:
		if x | y == y:
			a += 1
			break
		a += 1
		x += 1
	while c != d:
		if c | d == d:
			b += 1
			break
		b += 1
		d += 1
	print(min(a, b))


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	cnt = 1
	(ta, tb) = (a, b)
	while cnt < b - a:
		if ta | tb == tb:
			break
		tb += 1
		cnt += 1
	cnt2 = 1
	(ta, tb) = (a, b)
	while cnt2 < b - a:
		if ta | tb == tb:
			break
		ta += 1
		cnt2 += 1
	print(min({b - a, cnt, cnt2}))


t = int(input())
for T in range(t):
	(a, b) = [int(x) for x in input().split()]
	x = a
	y = b
	n = b
	ans = b - a
	while n > 0:
		n -= 1
		if x | y == y:
			ans = min(ans, b - n)
			break
		x += 1
	n = b
	x = a
	y = b
	while n > 0:
		n -= 1
		if x | y == y:
			ans = min(ans, b - n)
			break
		y += 1
	print(ans)


import sys

def f(a, b):
	if a == b:
		return 0
	if a | b == b:
		return 1
	for i in range(29, -1, -1):
		if b >> i & 1 == 0 and a >> i & 1 == 1:
			for j in range(i + 1, 30):
				if b >> j & 1 == 1 and a >> j & 1 == 0:
					x = (a | (1 << j) - 1) + 1
					if x == b:
						return x - a
					else:
						return x - a + 1
			raise Exception('wut1' + str(a) + ' ' + str(b))
	raise Exception('wut' + str(a) + ' ' + str(b))

def solve():
	inp = sys.stdin.readline
	(a, b) = map(int, inp().split())
	r = f(a, b)
	x = b
	while True:
		r = min(r, f(a, x) + x - b)
		r = min(r, (a | x) - b + 1)
		if x & x - 1 == 0:
			break
		x += x ^ x & x - 1
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


try:
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		minimum = []
		if a == b:
			print(0)
		elif a | b == a or a | b == b:
			print(1)
		else:
			diff = abs(a - b)
			minimum.append(diff)
			steps = 0
			mini = min(a, b)
			maxi = max(a, b)
			for i in range(0, maxi):
				steps += 1
				mini += 1
				if mini | maxi == mini or mini | maxi == maxi:
					steps += 1
					break
			minimum.append(steps)
			steps = 0
			mini = min(a, b)
			maxi = max(a, b)
			for i in range(0, maxi):
				steps += 1
				maxi += 1
				if mini | maxi == mini or mini | maxi == maxi:
					steps += 1
					break
			minimum.append(steps)
			print(min(minimum))
except:
	pass


def solve():
	(a, b) = map(int, input().split())
	if abs(a - b) == 1 or a | b == b:
		print(1)
		return
	store_a = a
	ans = min(abs(a - b), abs((a | b) - b) + 1)
	count = 0
	while a <= b:
		count += 1
		temp = abs((a | b) - b) + count
		if temp < ans:
			ans = temp
		a += 1
	a = store_a
	count = 0
	temp_or = a | b
	while b <= temp_or:
		count += 1
		temp = abs((a | b) - b) + count
		if temp < ans:
			ans = temp
		b += 1
	print(ans)
	return
for _ in range(int(input())):
	solve()


import math
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	min_n = b - a
	for i in range(b - a):
		answ = (a + i | b) - b + i + 1
		if answ < min_n:
			min_n = answ
	for i in range(min_n):
		answ = (a | b + i) - (b + i) + i + 1
		if answ < min_n:
			min_n = answ
	print(min_n)


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(str, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	(a, b) = M()
	ans = b - a
	for i in range(b - a):
		if a + i | b == b or b + i | a == b + i:
			ans = min(ans, i + 1)
	print(ans)


import math
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	ans = math.inf
	for i in range(a, b):
		ans = min(ans, i - a + ((i | b) - b) + 1)
	ans = min(ans, b - a)
	for i in range(1000001):
		if a | b + i == b + i:
			ans = min(ans, 1 + i)
			break
	print(ans)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	aa = a
	mn = 1000000007
	while aa < b:
		if aa | b == b:
			mn = min(mn, aa - a + 1)
		aa += 1
	bb = b
	while bb < 2 * b:
		if bb | a == bb:
			mn = min(mn, bb - b + 1)
		bb += 1
	print(min(mn, b - a))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	best = b - a
	for i in range(b - a):
		a1 = a + i | b
		best = min(best, i + 1 + a1 - b)
		b1 = b + i
		a1 = a | b1
		best = min(best, i + 1 + a1 - b1)
		if i > best - 1:
			break
	print(best)


def main2():

	def gen():
		r = 1
		while True:
			r += 1
			l = 1
			while l < r:
				yield (l, r)
				l += 1
	for (i, x) in enumerate(gen()):
		if i > 100:
			break
		print(i + 1, x)
	quit()
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	result = b - a
	for i in range(b - a):
		na = a + i
		na = na | b
		cur = i + 1 + (na - b)
		result = min(result, cur)
	bit = 1 << 32
	while bit:
		if a & bit and (not b & bit):
			break
		bit = bit >> 1
	mask = (bit << 1) - 1
	a = a & mask
	b = b & mask
	result = min(result, abs(a - b) + 1)
	print(result)