Given two integers A and B, the task is to find an integer X such that (X XOR A) is minimum possible and the count of set bit in X is equal to the count of set bits in B.
Example 1:
Input: 
A = 3, B = 5
Output: 3
Explanation:
Binary(A) = Binary(3) = 011
Binary(B) = Binary(5) = 101
The XOR will be minimum when x = 3
i.e. (3 XOR 3) = 0 and the number
of set bits in 3 is equal
to the number of set bits in 5.
Example 2:
Input: 
A = 7, B = 12
Output: 6
Explanation:
(7)_{2}= 111
(12)_{2}= 1100
The XOR will be minimum when x = 6 
i.e. (6 XOR 7) = 1 and the number 
of set bits in 6 is equal to the 
number of set bits in 12.
Your task :
You don't need to read input or print anything. Your task is to complete the function minVal() that takes integer A and B as input and returns the value of X according to the question.
 
Expected Time Complexity : O(log N)
Expected Auxiliary Space : O(1)
 
Constraints :
0 <= A, B <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    def minVal(self, a, b):

        #code here

Solutions:
class Solution:

	def minVal(self, a, b):
		a = bin(a)[2:]
		b = bin(b)[2:]
		count = 0
		for i in b:
			count += i == '1'
		s = ['0' for i in range(len(a))]
		for i in range(len(a)):
			if a[i] == '1' and count > 0:
				s[i] = '1'
				count -= 1
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '0' and count > 0:
				s[i] = '1'
				count -= 1
		if count > 0:
			s.reverse()
			while count:
				s.append('1')
				count -= 1
		ans = 0
		s.reverse()
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '1':
				ans += 1 << i
		return ans


class Solution:

	def minVal(self, a, b):
		x = bin(b)[2:]
		z = x.count('1')
		ans = []
		for i in bin(a)[2:]:
			if i == '0':
				ans += [i]
			elif z > 0:
				ans += ['1']
				z -= 1
			else:
				ans += ['0']
		if z > 0:
			for i in range(len(ans) - 1, -1, -1):
				if ans[i] == '0':
					ans[i] = '1'
					z -= 1
				if z == 0:
					break
		ans = ['1'] * z + ans
		return int(''.join(map(str, ans)), 2)


class Solution:

	def minVal(self, a, b):

		def f(b):
			cnt = 0
			while b:
				b &= b - 1
				cnt += 1
			return cnt
		ans = []
		bits = f(b)
		l = list(bin(a)[2:])
		for i in l:
			if i == '1' and bits > 0:
				bits -= 1
				ans += ['1']
			elif i == '1' and bits == 0 or (i == '0' and bits == 0):
				ans += ['0']
			elif i == '0':
				ans += ['0']
		for i in range(len(l) - 1, -1, -1):
			if bits > 0 and ans[i] == '0':
				ans[i] = '1'
				bits -= 1
		temp = []
		while bits > 0:
			temp += ['1']
			bits -= 1
		ans = temp + ans
		return int(''.join(ans), 2)


class Solution:

	def minVal(self, a, b):
		x = 0
		c = 0
		k = 2 ** 32
		while k != 0:
			if b & k == k:
				c += 1
			k = k >> 1
		k = 2 ** 32
		while k != 0:
			if a & k == k and c != 0:
				x = x + k
				c -= 1
			k = k >> 1
		if c != 0:
			k = 1
			while c != 0:
				if x & k != k:
					x = x + k
					c -= 1
				k = k << 1
		return x


def countSetBits(num):
	count = 0
	while num > 0:
		if num & 1 > 0:
			count += 1
		num = num >> 1
	return count

def countNoOfBits(num):
	count = 0
	while num > 0:
		num = num >> 1
		count += 1
	return count

class Solution:

	def minVal(self, a, b):
		setA = countSetBits(a)
		setB = countSetBits(b)
		if setA == setB:
			ans = a
		else:
			new = a
			diff = abs(setA - setB)
			val = diff
			count = 0
			if setA > setB:
				while val > 0:
					if new & 1 != 0:
						val -= 1
					count += 1
					new = new >> 1
				for i in range(count):
					new = new << 1
				ans = new
			else:
				while val > 0:
					if new & 1 == 0:
						val -= 1
					count += 1
					new = new >> 1
				for i in range(count):
					new = new << 1
					new += 1
				ans = new
		return ans


class Solution:

	def minVal(self, a, b):
		setBits = bin(b).count('1')
		ans = 0
		for i in range(30, -1, -1):
			mask = 1 << i
			s = a & mask
			if s and setBits > 0:
				ans |= 1 << i
				setBits -= 1
		i = 0
		while setBits > 0:
			mask = 1 << i
			if ans & mask == 0:
				ans |= 1 << i
				setBits -= 1
			i += 1
		return ans


from math import log

class Solution:

	def minVal(self, a, b):
		c = 0
		while b:
			if b & 1:
				c += 1
			b >>= 1
		bit = 31
		res = 0
		for i in range(bit, -1, -1):
			res <<= 1
			if a & 1 << i and c >= 1:
				res |= 1
				c -= 1
		bit = 30
		if c > 0:
			for i in range(bit + 1):
				if a & 1 << i == 0 and c >= 1:
					res |= 1 << i
					c -= 1
		return res


class Solution:

	def minVal(self, a, b):
		s1 = bin(a)[2:]
		s2 = bin(b)[2:]
		c1 = s1.count('1')
		c2 = s2.count('1')
		if c1 == c2:
			return a
		elif c1 > c2:
			k = c2
			d = ''
			i = 0
			while k and i < len(s1):
				if s1[i] == '1':
					k -= 1
					d += '1'
				else:
					d += '0'
				i += 1
			d += '0' * (len(s1) - i)
			return int(d, 2)
		else:
			if len(s1) < c2:
				q = '1' * c2
				return int(q, 2)
			k = c2 - c1
			num = s1
			j = num[::-1]
			i = 0
			h = ''
			while k and i < len(s1):
				if j[i] == '0':
					h += '1'
					k -= 1
				else:
					h += j[i]
				i += 1
			h += j[i:]
			u = h[::-1]
			return int(u, 2)


class Solution:

	def minVal(self, a, b):
		(m, n) = (a, b)
		(c, d) = (0, 0)
		lna = 0
		while m:
			if m & 1:
				c += 1
			m = m >> 1
			lna += 1
		while n:
			if n & 1:
				d += 1
			n = n >> 1
		if c == d:
			return a
		elif lna < d:
			k = 1
			while d:
				d -= 1
				k = k << 1
			return k - 1
		elif c > d:
			m = a
			diff = c - d
			k = 1
			count = 0
			while diff:
				if m & 1:
					count += k
					diff -= 1
				m = m >> 1
				k = k << 1
			return a - count
		else:
			m = a
			diff = d - c
			k = 1
			count = 0
			while diff:
				if m & 1 == 0:
					count += k
					diff -= 1
				m = m >> 1
				k = k << 1
			return a + count


class Solution:

	def count(self, n):
		count = 0
		while n:
			(count, n) = (count + 1, n & n - 1)
		return count

	def minVal(self, a, b):
		a_count = self.count(a)
		b_count = self.count(b)
		a_bin = bin(a)[2:]
		if b_count <= a_count:
			a_bin = a_bin[::-1].replace('1', '0', a_count - b_count)[::-1]
		else:
			a_bin = a_bin[::-1].replace('0', '1', b_count - a_count)[::-1]
			a_bin = '1' * (b_count - len(a_bin)) + a_bin
		return int(a_bin, 2)


class Solution:

	def countSetBit(self, num):
		i = 0
		while num:
			num = num & num - 1
			i += 1
		return i

	def minVal(self, a, b):
		i = self.countSetBit(b)
		a = bin(a)[2:]
		s = ''
		for x in a:
			if x == '1' and i != 0:
				s += '1'
				i -= 1
			elif x == '1' or x == '0':
				s += '0'
			else:
				pass
		if i != 0:
			s = list(s[::-1])
			for x in range(len(s)):
				if s[x] == '0':
					s[x] = '1'
					i -= 1
				if i == 0:
					break
			s = ''.join(s)[::-1]
		if i != 0:
			s += '1' * i
		return int(s, 2)


class Solution:

	def minVal(self, a, b):
		l = []
		c = 0
		d = 0
		y = a
		while a != 0:
			c += a % 2
			l.append(str(a % 2))
			a = a // 2
		d = bin(b).count('1')
		if d == c:
			return y
		elif d < c:
			n = len(l)
			for i in range(n - 1, -1, -1):
				if d > 0 and l[i] == '1':
					l[i] = '0'
					d -= 1
			s = ''.join(l)
			return int(s[::-1], 2) ^ y
		for i in range(7):
			l.append('0')
		g = d - c
		for i in range(len(l)):
			if l[i] == '1':
				l[i] = '0'
			elif g > 0 and l[i] == '0':
				l[i] = '1'
				g -= 1
			else:
				pass
		s = ''.join(l)
		return int(s[::-1], 2) ^ y


class Solution:

	def minVal(self, a, b):
		b_setbits = self.total_set_bits(b)
		a_setbits = self.total_set_bits(a)
		if a_setbits > b_setbits:
			i = 0
			remove_bits = a_setbits - b_setbits
			while i < remove_bits:
				a = a & a - 1
				i += 1
			return a
		elif a_setbits < b_setbits:
			diff = b_setbits - a_setbits
			while diff:
				a = a | a + 1
				diff -= 1
			return a
		else:
			return a

	def total_set_bits(self, n):
		count = 0
		while n > 0:
			n = n & n - 1
			count += 1
		return count


class Solution:

	def count(self, a):
		cnt = 0
		while a:
			a = a & a - 1
			cnt += 1
		return cnt

	def fun(self, a, temp):
		cnt = 0
		i = 1
		while temp > 0:
			cnt += 1
			if a & i > 0:
				temp -= 1
			i = i << 1
		a = a >> cnt
		return a * 2 ** cnt

	def minVal(self, a, b):
		a1 = self.count(a)
		b1 = self.count(b)
		temp = a1 - b1
		if temp == 0:
			return a
		if temp < 0:
			i = 1
			res = 0
			temp = -1 * temp
			while temp > 0:
				if i & a == 0:
					res = res | i
					temp -= 1
				i = i << 1
			a = a | res
			return a
		a = self.fun(a, temp)
		return a


class Solution:

	def minVal(self, a, b):
		setb = bin(b)[2:].count('1')
		seta = bin(a)[2:].count('1')
		ans = 0
		for i in range(0, 32):
			mask = 1 << i
			set = a & mask
			if set == 0 and setb > seta:
				ans |= mask
				setb -= 1
			elif set and seta > setb:
				seta -= 1
			else:
				ans |= set
		return ans


class Solution:

	def minVal(self, a, b):
		temp = bin(a).count('1') - bin(b).count('1')
		ans = a
		if temp == 0:
			return ans
		elif temp > 0:
			for i in range(32):
				if not temp:
					break
				if 1 << i & a:
					ans ^= 1 << i
					temp -= 1
		else:
			for i in range(32):
				if not temp:
					break
				if not 1 << i & a:
					ans += 1 << i
					temp += 1
		return ans


class Solution:

	def minVal(self, a, b):
		set_bits = 0
		while b > 0:
			set_bits += b % 2
			b = b // 2
		x = 0
		for i in range(31, -1, -1):
			if set_bits > 0 and a & 1 << i:
				x = x ^ 1 << i
				set_bits -= 1
		if set_bits > 0:
			for i in range(32):
				if x & 1 << i == 0:
					x = x ^ 1 << i
					set_bits -= 1
					if set_bits == 0:
						break
		return x


class Solution:

	def minVal(self, a, b):
		b1 = bin(b)
		b1 = b1[2:len(b1)]
		count = 0
		for i in b1:
			if i == '1':
				count += 1
		a1 = bin(a)
		a1 = a1[2:len(a1)]
		res = []
		for i in a1:
			res.append(i)
		for i in range(len(a1)):
			if res[i] == '1' and count >= 1:
				count -= 1
			else:
				res[i] = '0'
		for i in range(len(a1) - 1, -1, -1):
			if count > 0 and res[i] != '1':
				res[i] = '1'
				count -= 1
		ans = ''
		for i in range(len(res)):
			ans += res[i]
		ans2 = ''
		while count >= 1:
			ans2 += '1'
			count -= 1
		r = 0
		ans = ans2 + ans
		ans = ans[::-1]
		for i in range(len(ans)):
			if ans[i] == '1':
				r += pow(2, i)
		return r


class Solution:

	def minVal(self, a, b):
		if b == 0:
			return 0
		setbit = 0
		while b:
			if b % 2:
				setbit += 1
			b = b // 2
		flag = False
		ans = 0
		for i in range(31, -1, -1):
			if not flag:
				if setbit == i + 1:
					ans += 2 ** setbit - 1
					setbit = 0
					break
				elif 1 << i & a:
					ans += 1 << i
					setbit -= 1
					flag = True
			elif flag:
				if setbit == i + 1:
					ans += 2 ** setbit - 1
					setbit = 0
					break
				elif 1 << i & a and setbit > 0:
					ans += 1 << i
					setbit -= 1
		return ans


class Solution:

	def minVal(self, a, b):
		c = 0
		s1 = bin(a)
		s2 = bin(b)
		s1 = s1[2:]
		s2 = s2[2:]
		c = 0
		for i in s2:
			if i == '1':
				c += 1
		ans = 0
		for i in range(31, -1, -1):
			if i == c - 1:
				return ans + (1 << i + 1) - 1
			if a & 1 << i and c:
				ans += 1 << i
				c -= 1
		return ans


class Solution:

	def minVal(self, a, b):
		(sa, sb) = (0, 0)
		(na, nb) = (a, b)
		while na != 0:
			sa += 1
			na &= na - 1
		while nb != 0:
			sb += 1
			nb &= nb - 1
		(na, nb) = (a, b)
		if sa == sb:
			return a
		elif sa > sb:
			for _ in range(sa - sb):
				na &= na - 1
			return na
		else:
			for _ in range(sb - sa):
				na |= na + 1
			return na


class Solution:

	def minVal(self, a, b):
		set_bits = 0
		while b > 0:
			set_bits += b % 2
			b = b // 2
		s = []
		for i in range(31, -1, -1):
			bit = a & 1 << i
			if bit and set_bits > 0:
				s.append('1')
				set_bits -= 1
			else:
				s.append('0')
		s = s[::-1]
		for i in range(32):
			if set_bits > 0:
				if s[i] == '0':
					s[i] = '1'
					set_bits -= 1
			else:
				break
		result = 0
		for i in range(32):
			result += 2 ** i * int(s[i])
		return result


class Solution:

	def minVal(self, a, b):
		B = b
		A = a
		count_set_bit_b = bin(b).count('1')
		result = 0
		i = 31
		while i >= 0 and count_set_bit_b > 0:
			if A & 1 << i > 0:
				result |= 1 << i
				count_set_bit_b -= 1
			i -= 1
		i = 0
		while i < 31 and count_set_bit_b > 0:
			if A & 1 << i == 0:
				result |= 1 << i
				count_set_bit_b -= 1
			i += 1
		return result


class Solution:

	def minVal(self, a, b):
		a = bin(a)[2:].zfill(32)
		b = bin(b)[2:].zfill(32)
		x = ['0' for i in range(32)]
		cb = b.count('1')
		i = 0
		while cb and i < 32:
			while i < 32 and a[i] == '0':
				i += 1
			if i == 32:
				break
			x[i] = '1'
			i += 1
			cb -= 1
		i = 31
		while cb:
			while i >= 0 and x[i] == '1':
				i -= 1
			x[i] = '1'
			i -= 1
			cb -= 1
		return int(''.join(x), 2)


class Solution:

	def minVal(self, a, b):
		count_bit_b = 0
		while b:
			count_bit_b += b % 2
			b //= 2
		ans = 0
		for i in range(31, -1, -1):
			if a & 1 << i:
				ans |= 1 << i
				count_bit_b -= 1
			if count_bit_b == 0:
				break
		for i in range(0, 32):
			if count_bit_b == 0:
				break
			if a & 1 << i == 0:
				ans |= 1 << i
				count_bit_b -= 1
		return ans


class Solution:

	def minVal(self, a, b):
		a = bin(a)[2:]
		b = bin(b)[2:]
		count = 0
		for i in b:
			count += i == '1'
		s = ['0' for i in range(len(a))]
		for i in range(len(a)):
			if a[i] == '1' and count > 0:
				s[i] = '1'
				count -= 1
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '0' and count > 0:
				s[i] = '1'
				count -= 1
		if count > 0:
			s.reverse()
			while count:
				s.append('1')
				count -= 1
		ans = 0
		s.reverse()
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '1':
				ans += 1 << i
		return ans
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		a = int(input())
		b = int(input())
		ob = Solution()
		print(ob.minVal(a, b))


def set_bits(n):
	k = 0
	while n:
		n = n ^ n & -n
		k += 1
	return k

class Solution:

	def minVal(self, a, b):
		x = set_bits(a)
		y = set_bits(b)
		ans = 0
		if x == y:
			ans = a
		else:
			for i in range(32):
				mask = 1 << i
				se = a & mask
				if se == 0 and y > x:
					ans |= mask
					y -= 1
				elif se and x > y:
					x -= 1
				else:
					ans |= se
		return ans
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		a = int(input())
		b = int(input())
		ob = Solution()
		print(ob.minVal(a, b))


class Solution:

	def countSetBits(self, n):
		count = 0
		while n:
			n &= n - 1
			count += 1
		return count

	def minVal(self, a, b):
		minsetbitsA = self.countSetBits(a)
		minsetbitsB = self.countSetBits(b)
		if minsetbitsA == minsetbitsB:
			return a
		elif minsetbitsA > minsetbitsB:
			bitsToset = minsetbitsA - minsetbitsB
			while bitsToset:
				a = a - (a & ~(a - 1))
				bitsToset -= 1
			return a
		else:
			bitsToset = minsetbitsB - minsetbitsA
			abin = bin(a)[2:]
			iter = 0
			while bitsToset:
				if -1 * (-1 - iter) > len(abin):
					a = a + 2 ** iter
					bitsToset -= 1
				elif abin[-1 - iter] == '0':
					a = a + 2 ** iter
					bitsToset -= 1
				iter += 1
			return a
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		a = int(input())
		b = int(input())
		ob = Solution()
		print(ob.minVal(a, b))


class Solution:

	def minVal(self, a, b):
		ans = 0
		totalb = bin(b)[2:].count('1')
		for i in range(31, -1, -1):
			if totalb == 0:
				return ans
			if a & 1 << i:
				ans |= 1 << i
				totalb -= 1
		for i in range(32):
			if totalb == 0:
				return ans
			if a & 1 << i == 0:
				ans |= 1 << i
				totalb -= 1


class Solution:

	def minVal(self, a, b):
		set_in_b = bin(b)[2:].count('1')
		set_in_a = bin(a)[2:].count('1')
		bi_a = len(bin(a)[2:])
		bi_b = len(bin(b)[2:])
		if set_in_a == set_in_b:
			return a
		if set_in_a > set_in_b:
			ans = list('0' * abs(bi_b - bi_a) + bin(a)[2:])
			for i in range(len(ans) - 1, -1, -1):
				if ans.count('1') == set_in_b:
					break
				if ans[i] == '1':
					ans[i] = '0'
		else:
			ans = list('0' * abs(bi_b - bi_a) + bin(a)[2:])
			for i in range(len(ans) - 1, -1, -1):
				if ans.count('1') == set_in_b:
					break
				if ans[i] == '0':
					ans[i] = '1'
		return int(''.join(ans), 2)


class Solution:

	def minVal(self, a, b):
		bit_a = 0
		bit_b = 0
		tmp_a = a
		while tmp_a != 0:
			bit_a += 1
			tmp_a = tmp_a & tmp_a - 1
		tmp_b = b
		while tmp_b != 0:
			bit_b += 1
			tmp_b = tmp_b & tmp_b - 1
		if bit_a == bit_b:
			num = a
		elif bit_a > bit_b:
			num = a
			mask = 1
			while bit_a != bit_b:
				if num & mask:
					num = num ^ mask
					bit_a -= 1
				mask = mask << 1
		else:
			num = a
			mask = 1
			while bit_a != bit_b:
				if num & mask == 0:
					num = num ^ mask
					bit_a += 1
				mask = mask << 1
		return num


class Solution:

	def minVal(self, a, b):
		if b == 0:
			return 0
		if a > b:
			n = len(bin(a)) - 2
		else:
			n = len(bin(b)) - 2
		(a, b) = (bin(a)[2:], bin(b)[2:])
		bc = b.count('1')
		ac = a.count('1')
		if ac == bc:
			return int(a, 2)
		if ac < bc:
			(p, i) = (bc - ac, 1)
			s = list(a)
			while p:
				try:
					if s[-i] == '0':
						s[-i] = '1'
						p -= 1
					i += 1
				except:
					s = ['1' for z in range(p)] + s
					break
			return int(''.join(s), 2)
		else:
			s = ['0' for i in range(n)]
			if len(a) != n:
				a = '0' * (n - len(a)) + a
			for i in range(n):
				if a[i] == '1':
					s[i] = '1'
					bc -= 1
				if not bc:
					break
			return int(''.join(s), 2)


class Solution:

	def minVal(self, a, b):
		a = bin(a)[2:]
		a = '0' * (32 - len(a)) + a
		x = bin(b)[2:].count('1')
		ans = [0 for _ in range(32)]
		for i in range(32):
			if x == 0:
				break
			if a[i] == '1':
				ans[i] = 1
				x -= 1
		ans = ans[::-1]
		for i in range(32):
			if x == 0:
				break
			if ans[i] == 0:
				ans[i] = 1
				x -= 1
		t = 0
		for i in range(32):
			t += ans[i] * 2 ** i
		return t


class Solution:

	def sb(self, n):
		c = 0
		while n:
			n &= n - 1
			c += 1
		return c

	def minVal(self, a, b):
		mina = self.sb(a)
		minb = self.sb(b)
		if mina == minb:
			return a
		elif mina > minb:
			bs = mina - minb
			while bs:
				a -= a & ~(a - 1)
				bs -= 1
			return a
		else:
			bs = minb - mina
			abin = bin(a)[2:]
			i = 0
			while bs:
				if -1 * (-1 - i) > len(abin):
					a += 2 ** i
					bs -= 1
				elif abin[-1 - i] == '0':
					a += 2 ** i
					bs -= 1
				i += 1
			return a


class Solution:

	def minVal(self, a, b):
		cb = 0
		for i in range(32):
			if 1 << i & b:
				cb += 1
		if cb == 0:
			return 0
		x = 0
		for i in range(31, -1, -1):
			if 1 << i & a:
				x ^= 1 << i
				cb -= 1
				if cb == 0:
					return x
		for i in range(32):
			if x & 1 << i == 0:
				x ^= 1 << i
				cb -= 1
				if cb == 0:
					return x


def bitcount(a):
	c = 0
	while a:
		c += a & 1
		a >>= 1
	return c

def topBitsIn(a, n):
	mask = 1
	while mask < a:
		mask <<= 1
	res = 0
	taken = 0
	while taken < n:
		if a & mask != 0:
			res |= mask
			taken += 1
		mask >>= 1
		if mask == 0:
			raise ValueError()
	return res

def bottomBitsNotIn(a, n):
	mask = 1
	taken = 0
	res = 0
	while taken < n:
		if a & mask == 0:
			res |= mask
			taken += 1
		mask <<= 1
	return res

class Solution:

	def minVal(self, a, b):
		ac = bitcount(a)
		needed = bitcount(b)
		if needed < ac:
			return topBitsIn(a, needed)
		return a | bottomBitsNotIn(a, needed - ac)


class Solution:

	def cout(self, a):
		p = bin(a)[2:]
		return p.count('1')

	def minVal(self, a, b):
		ma = self.cout(a)
		mb = self.cout(b)
		if ma == mb:
			return a
		elif ma > mb:
			k = ma - mb
			while k:
				a = a - (a & ~(a - 1))
				k -= 1
			return a
		else:
			k = mb - ma
			hig = bin(a)[2:]
			i = 0
			while k:
				if -1 * (-1 - i) > len(hig):
					a = a + 2 ** i
					k -= 1
				elif hig[-1 - i] == '0':
					a = a + 2 ** i
					k -= 1
				i += 1
		return a


class Solution:

	def countBits(self, n):
		cnt = 0
		while n:
			n &= n - 1
			cnt += 1
		return cnt

	def minVal(self, a, b):
		setbits = self.countBits(b)
		ans = 0
		for i in range(31, -1, -1):
			bit = a & 1 << i
			if bit:
				ans = ans | 1 << i
				setbits -= 1
			if setbits == 0:
				return ans
		i = 0
		while setbits:
			bit = a & 1 << i
			if bit == 0:
				ans = ans | 1 << i
				setbits -= 1
			i += 1
		return ans


class Solution:

	def bitCount(self, a):
		c = 0
		for i in range(0, 34):
			if a & 1 << i:
				c += 1
		return c

	def minVal(self, a, b):
		s = 0
		x = self.bitCount(b)
		for i in range(33, -1, -1):
			if a & 1 << i and x != 0:
				s = s + (1 << i)
				x -= 1
		for i in range(0, 34):
			if a & 1 << i == 0 and x != 0:
				s = s + (1 << i)
				x -= 1
		return s


class Solution:

	def minVal(self, a, b):
		res = a
		a1 = a
		b1 = b
		n = 0
		m = 0
		length = 0
		while a1 > 0:
			n += a1 % 2
			length += 1
			a1 //= 2
		while b1 > 0:
			m += b1 % 2
			b1 //= 2
		if n == m:
			res = a
		elif n > m:
			a1 = a
			k = n - m
			i = 0
			while k > 0:
				i += 1
				if a1 % 2 == 1:
					k -= 1
				a1 //= 2
			for j in range(i):
				a1 *= 2
			res = a1
		elif length <= m:
			res = 2 ** m - 1
		else:
			a1 = a
			k = m - n
			count = 0
			while k > 0:
				if a1 % 2 == 0:
					k -= 1
					res += 2 ** count
				a1 //= 2
				count += 1
		return res


class Solution:

	def minVal(self, a, b):
		setbits = bin(b).count('1')
		res = 0
		for i in range(30, -1, -1):
			if a & 1 << i and setbits:
				res |= 1 << i
				setbits -= 1
		i = 0
		while setbits:
			if not res & 1 << i:
				res |= 1 << i
				setbits -= 1
			i += 1
		return res


def popcnt(x):
	cnt = 0
	while x != 0:
		cnt += x & 1
		x >>= 1
	return cnt

class Solution:

	def minVal(self, a, b):
		nbits = popcnt(b)
		x = a
		mask = 1
		while popcnt(x) < nbits:
			x |= mask
			mask <<= 1
		mask = 1
		while popcnt(x) > nbits:
			x &= ~mask
			mask <<= 1
		return x


class Solution:

	def minVal(self, a, b):
		b = bin(b)[2:]
		a = bin(a)[2:]
		c = 0
		for i in b:
			if i == '1':
				c += 1
		arr = [0 for i in range(len(a))]
		i = 0
		while i < len(a) and c > 0:
			if a[i] == '1':
				arr[i] = 1
				c -= 1
			i += 1
		i -= 1
		while i >= 0 and c != 0:
			if arr[i] == 0:
				arr[i] = 1
				c -= 1
			i -= 1
		arr += [1] * c
		ans = 0
		arr = arr[::-1]
		for i in range(len(arr)):
			if arr[i] == 1:
				ans += 2 ** i
		return ans


class Solution:

	def countSetBits(self, n):
		count = 0
		while n:
			n &= n - 1
			count += 1
		return count

	def minVal(self, a, b):
		minsetbitsA = self.countSetBits(a)
		minsetbitsB = self.countSetBits(b)
		if minsetbitsA == minsetbitsB:
			return a
		elif minsetbitsA > minsetbitsB:
			bitsToset = minsetbitsA - minsetbitsB
			while bitsToset:
				a = a - (a & ~(a - 1))
				bitsToset -= 1
			return a
		else:
			bitsToset = minsetbitsB - minsetbitsA
			abin = bin(a)[2:]
			iter = 0
			while bitsToset:
				if -1 * (-1 - iter) > len(abin):
					a = a + 2 ** iter
					bitsToset -= 1
				elif abin[-1 - iter] == '0':
					a = a + 2 ** iter
					bitsToset -= 1
				iter += 1
			return a


class Solution:

	def minVal(self, a, b):
		c = b
		bit = 0
		while c > 0:
			bit += c & 1
			c >>= 1
		l = []
		for i in range(30, -1, -1):
			if 1 << i & a:
				l.append(1)
			else:
				l.append(0)
		l = l[::-1]
		n = len(l)
		l1 = [0] * n
		i = n - 1
		while bit > 0 and i >= 0:
			if l[i] == 1:
				bit -= 1
				l1[i] = 1
			i -= 1
		i = 0
		while bit > 0:
			if l1[i] == 0:
				l1[i] = 1
				bit -= 1
			i += 1
		c = 0
		ans = 0
		for i in l1:
			ans += i * (1 << c)
			c += 1
		return ans


class Solution:

	def minVal(self, a, b):
		a_bin = str(bin(a))
		b_bin = str(bin(b))
		a_bin = a_bin[2:]
		b_bin = b_bin[2:]
		cnt = 0
		cnt1 = 0
		for i in range(len(b_bin)):
			if b_bin[i] == '1':
				cnt = cnt + 1
		for i in range(len(a_bin)):
			if a_bin[i] == '1':
				cnt1 = cnt1 + 1
		if cnt > len(a_bin):
			dif = cnt - len(a_bin)
			temp = '0' * dif
			a_bin = temp + a_bin
		temp = a_bin.replace('1', 'x', cnt)
		t1 = temp.replace('1', '0')
		res = t1.replace('x', '1')
		if cnt1 < cnt:
			d = cnt - cnt1
			rev = res[::-1]
			t2 = rev.replace('0', '1', d)
			res = t2[::-1]
		return int(res, base=2)


class Solution:

	def minVal(self, a, b):
		a_setbits = bin(a)[2:].count('1')
		b_setbits = bin(b)[2:].count('1')
		diff = abs(a_setbits - b_setbits)
		if a_setbits == b_setbits:
			return a
		elif a_setbits > b_setbits:
			while diff:
				a = a & a - 1
				diff -= 1
		else:
			while diff:
				a = a | a + 1
				diff -= 1
		return a


class Solution:

	def minVal(self, a, b):
		B = bin(b)[2:]
		b_one = B.count('1')
		A = bin(a)[2:]
		ans = []
		for i in range(len(A)):
			if A[i] == '1':
				if b_one:
					ans.append('1')
					b_one -= 1
				else:
					ans.append('0')
			else:
				ans.append('0')
		for j in range(len(A) - 1, -1, -1):
			if ans[j] == '0':
				if b_one:
					ans[j] = '1'
					b_one -= 1
		if b_one:
			ans = ['1'] * b_one + ans
		x = ''.join(ans)
		return int(x, 2)


class Solution:

	def countSetBits(self, n):
		count = 0
		while n:
			n = n & n - 1
			count += 1
		return count

	def minVal(self, a, b):
		x = a
		diff = self.countSetBits(b) - self.countSetBits(a)
		mask = 1
		if diff >= 0:
			while diff:
				if x & mask == 0:
					x = x | mask
					diff -= 1
				mask <<= 1
			return x
		elif diff < 0:
			diff = -diff
			while diff:
				if x & mask:
					x = x & ~mask
					diff -= 1
				mask <<= 1
			return x


class Solution:

	def minVal(self, a, b):
		n1 = bin(a)[2:]
		ans = []
		n2 = bin(b).count('1')
		for i in n1:
			if n2 == 0:
				break
			if i == '1':
				ans.append('1')
				n2 -= 1
			else:
				ans.append('0')
		if n2 > 0:
			for i in range(len(ans) - 1, -1, -1):
				if ans[i] == '0':
					if n2 > 0:
						ans[i] = '1'
						n2 -= 1
		if n2 > 0:
			ans = ['1'] * n2 + ans
		if len(ans) < len(n1):
			for i in range(len(ans), len(n1)):
				ans.append('0')
		res = 0
		c = 0
		for i in range(len(ans) - 1, -1, -1):
			if ans[i] == '1':
				res += 2 ** c
			c += 1
		return res


def count(num):
	c = 0
	while num > 0:
		if num % 2 == 1:
			c += 1
		num = num // 2
	return c

class Solution:

	def minVal(self, a, b):
		c1 = count(a)
		c2 = count(b)
		if c1 == c2:
			return a
		elif c1 > c2:
			diff = c1 - c2
			while diff > 0:
				a = a & a - 1
				diff -= 1
			return a
		else:
			diff = c2 - c1
			while diff > 0:
				a = a | a + 1
				diff -= 1
			return a


class Solution:

	def countOnes(self, n):
		res = 0
		while n > 0:
			if n % 2 == 1:
				res += 1
			n //= 2
		return res

	def minVal(self, a, b):
		a1 = self.countOnes(a)
		b1 = self.countOnes(b)
		if a1 == b1:
			return a
		a2 = list(bin(a).replace('0b', ''))
		b2 = list(bin(b).replace('0b', ''))
		a3 = a2.copy()
		if a1 > b1:
			i = a1 - b1
			for j in range(len(a3) - 1, -1, -1):
				if a3[j] == '1':
					a3[j] = '0'
					i -= 1
				if i == 0:
					break
		elif a1 < b1:
			x = len(a2)
			y = len(b2)
			if x > y:
				for i in range(x - y):
					b2.insert(0, '0')
			if x < y:
				for i in range(y - x):
					a2.insert(0, '0')
			i = b1 - a1
			a3 = a2.copy()
			for j in range(len(a3) - 1, -1, -1):
				if a3[j] == '0':
					a3[j] = '1'
					i -= 1
				if i == 0:
					break
		a3.insert(0, 'b')
		a3.insert(0, '0')
		a3 = ''.join(a3)
		a3 = int(a3, 2)
		return a3


class Solution:

	def minVal(self, a, b):
		a_bin = []
		b_bin = []
		while a >= 1:
			a_bin.append(a % 2)
			a = a // 2
		a_bin.reverse()
		while b >= 1:
			b_bin.append(b % 2)
			b = b // 2
		b_bin.reverse()
		if a_bin.count(1) == b_bin.count(1):
			x = a_bin
		elif a_bin.count(1) > b_bin.count(1):
			x = a_bin
			for i in range(1, len(x) + 1):
				if x[-i] == 1:
					x[-i] = 0
					if x.count(1) == b_bin.count(1):
						break
		elif a_bin.count(1) < b_bin.count(1):
			x = a_bin
			for i in range(1, len(x) + 1):
				if x[-i] == 0:
					x[-i] = 1
					if x.count(1) == b_bin.count(1):
						break
			if len(x) < b_bin.count(1):
				for j in range(b_bin.count(1) - x.count(1)):
					x.append(1)
		num = 0
		for i in range(1, len(x) + 1):
			num = num + x[-i] * 2 ** (i - 1)
		return num


class Solution:

	def minVal(self, a, b):
		a1 = bin(a)[2:]
		b1 = bin(b)[2:]
		sb = 0
		for i in b1:
			if i == '1':
				sb += 1
		out = ''
		f = 0
		n = len(a1)
		if sb >= n:
			ans = 2 ** sb - 1
			return ans
		for i in range(n):
			k = '0'
			if sb == n - i:
				f = 1
			if (f == 1 or a1[i] == '1') and sb > 0:
				k = '1'
				sb -= 1
			out += k
		p = 1
		ans = 0
		for i in range(n - 1, -1, -1):
			ans += p * int(out[i])
			p = p * 2
		return ans


class Solution:

	@staticmethod
	def get_set_bit_indices(v: int):
		(indices, cur_index) = ([], 0)
		while v:
			if v & 1:
				indices.append(cur_index)
			v >>= 1
			cur_index += 1
		return indices

	def minVal(self, a: int, b: int):
		if b == 0:
			return 0
		bit_count = len(self.get_set_bit_indices(b))
		indices = self.get_set_bit_indices(a)
		ans = 0
		for i in indices[-bit_count:]:
			ans |= 1 << i
		diff = bit_count - len(indices)
		(cur, indices_set) = (0, set(indices))
		while diff > 0:
			set_bit = 1 << cur
			if cur not in indices_set and ans & set_bit == 0:
				ans |= set_bit
				diff -= 1
			cur += 1
		return ans


class Solution:

	def minVal(self, a, b):
		if b == 0:
			return b
		countb = 0
		for i in bin(b).replace('0b', ''):
			if i == '1':
				countb += 1
		z = 0
		bina = bin(a).replace('0b', '')
		for i in range(len(bina)):
			if bina[i] == '1':
				z += int('1' + '0' * len(bina[i + 1:]))
				countb -= 1
			if countb == 0:
				break
		if countb > 0:
			for i in range(len(bina) - 1, -1, -1):
				if bina[i] == '0':
					z += int('1' + '0' * len(bina[i + 1:]))
					countb -= 1
				if countb == 0:
					break
		if countb > 0:
			z += int('1' * countb + '0' * len(bina))
		return int(str(z), 2)


class Solution:

	def minVal(self, a, b):
		setbit = bin(b).count('1')
		ans = 0
		for i in range(31, -1, -1):
			if setbit:
				mask = 1 << i
				if a & mask:
					ans |= mask
					setbit -= 1
		for i in range(0, 31):
			if setbit:
				mask = 1 << i
				if a & mask == 0:
					ans |= mask
					setbit -= 1
		return ans


class Solution:

	def minVal(self, a, b):
		setBits = bin(b).count('1')
		ans = 0
		for i in range(30, -1, -1):
			mask = 1 << i
			s = a & mask
			if s and setBits > 0:
				ans |= 1 << i
				setBits -= 1
		for i in range(31):
			if setBits > 0:
				mask = 1 << i
				s = ans & mask
				if not s:
					ans |= 1 << i
					setBits -= 1
			else:
				break
		return ans


class Solution:

	def ones(self, n):
		counter = 0
		while n > 0:
			counter += n % 2
			n = n >> 1
		return counter

	def minVal(self, a, b):
		o = self.ones(b)
		bina = format(a, 'b')
		binb = format(b, 'b')
		binf = format(a, 'b').zfill(max(len(binb), len(bina)))
		res = ''
		for i in range(len(binf)):
			if o > 0 and binf[i] == '1':
				res += '1'
				o -= 1
			elif o > 0 and len(binf) - i <= o:
				res += '1'
				o -= 1
			else:
				res += '0'
		return int(res, 2)


class Solution:

	def minVal(self, a, b):

		def cnt(b):
			c = 0
			while b:
				b = b & b - 1
				c += 1
			return c
		ac = cnt(a)
		ab = cnt(b)
		d = abs(ac - ab)
		if d == 0:
			return a
		elif ac > ab:
			while d > 0:
				a = a & a - 1
				d -= 1
		else:
			while d > 0:
				a |= a + 1
				d -= 1
		return a


class Solution:

	def binaryToDecimal(self, binary_num):
		dec_num = 0
		m = 1
		for i in range(len(binary_num) - 1, -1, -1):
			digit = int(binary_num[i])
			dec_num = dec_num + digit * m
			m = m * 2
		return dec_num

	def minVal(self, A, B):
		a = []
		b = []
		while A > 0:
			bit = A % 2
			a.insert(0, bit)
			A = int(A / 2)
		while B > 0:
			bit = B % 2
			b.insert(0, bit)
			B = int(B / 2)
		count1 = 0
		count2 = 0
		r = []
		diff = b.count(1) - a.count(1)
		count0 = a.count(0)
		for i in range(0, len(a), 1):
			x = a[i]
			if x == 1:
				if count1 < b.count(1):
					r.append(1)
					count1 = count1 + 1
				else:
					r.append(0)
			elif x == 0:
				if diff >= count0:
					r.append(1)
					count1 = count1 + 1
					diff = diff - 1
					count0 = count0 - 1
				else:
					r.append(0)
					count0 = count0 - 1
					count2 = count2 + 1
		while r.count(1) < b.count(1):
			r.append(1)
		return self.binaryToDecimal(binary_num=r)


class Solution:

	def minVal(self, a, b):
		(ca, cb) = (0, 0)
		ba = [0 for i in range(31)]
		bb = [0 for i in range(31)]
		ans = [0 for i in range(31)]
		for i in range(31):
			if b & 1 << i:
				bb[i] = 1
				cb += 1
			if a & 1 << i:
				ba[i] = 1
				ca += 1
		if ca == cb:
			return a
		else:
			temp = cb
			for i in range(30, -1, -1):
				if ba[i] == 1 and temp > 0:
					ans[i] = 1
					temp -= 1
				else:
					ans[i] = 0
			for i in range(31):
				if temp == 0:
					break
				if ans[i] == 0:
					ans[i] = 1
					temp -= 1
			total = 0
			for i in range(31):
				if ans[i] == 1:
					total += 1 << i
			return total


class Solution:

	def minVal(self, a, b):
		ba = db(a)
		c1 = ba.count('1')
		c2 = db(b).count('1')
		if c1 == c2:
			return a
		if c2 > c1:
			n = ''
			j = c2 - c1
			n = [i for i in ba]
			for i in range(len(ba) - 1, -1, -1):
				if j > 0:
					if ba[i] == '0':
						j = j - 1
						n[i] = '1'
			v = ''
			for i in n:
				v = v + i
			if j > 0:
				for i in range(j):
					v = v + '1'
			return int(v, 2)
		if c1 > c2:
			n = ''
			l = len(ba)
			k = 0
			j = c2
			for i in range(l):
				if j > 0:
					if ba[i] == '1':
						j = j - 1
						n = n + '1'
					else:
						n = n + '0'
				else:
					n = n + '0'
			return int(n, 2)

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


class Solution:

	def minVal(self, a, b):
		b1 = bin(a)
		b2 = bin(b)
		count2 = b2.count('1')
		res = 0
		x = b1[2:]
		n = len(x)
		count1 = x.count('1')
		if count2 <= count1:
			for i in range(n):
				if count2 == 0:
					break
				if x[i] == '1':
					res += 2 ** (n - i - 1)
					count2 -= 1
		else:
			new = [0] * n
			for i in range(n):
				if x[i] == '1':
					new[i] = 1
					count2 -= 1
				if count2 == 0:
					break
			if count2 > 0:
				for i in range(len(new) - 1, -1, -1):
					if new[i] == 0:
						new[i] = 1
						count2 -= 1
					if count2 == 0:
						break
			res = 0
			for i in range(len(new)):
				if new[i] == 1:
					res += 2 ** (len(new) - i - 1)
			j = len(new)
			while count2 > 0:
				res += 2 ** j
				j += 1
				count2 -= 1
		return res