You are given three non-negative integers $X$, $Y$ and $N$. Find the number of integers $Z$ such that $0 \le Z \le N$ and $(X \oplus Z) < (Y \oplus Z)$, where $\oplus$ denotes the bitwise XOR operation.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains three space-separated integers $X$, $Y$ and $N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of integers $Z$ which satisfy all conditions.

-----Constraints-----
- $1 \le T \le 1,000$
- $0 \le X, Y, N \le 2^{30} - 1$

-----Subtasks-----
Subtask #1 (5 points): $X, Y, N \le 2^6 - 1$
Subtask #2 (95 points): original constraints

-----Example Input-----
3
1 2 10
2 1 10
0 0 7

-----Example Output-----
6
5
0

Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(x, y, n) = [int(i) for i in input().split()]
	bx = list(bin(x))
	by = list(bin(y))
	bx.remove(bx[0])
	bx.remove(bx[0])
	by.remove(by[0])
	by.remove(by[0])
	lx = len(bx)
	ly = len(by)
	index = 0
	flag = 2
	k = -1
	if lx != ly:
		index = max(lx, ly)
		if (n + 1) % 2 ** index >= 2 ** (index - 1):
			k = 2 ** (index - 1)
		else:
			k = (n + 1) % 2 ** index
		if lx < ly:
			print(int((n + 1) / 2 ** index) * 2 ** (index - 1) + k)
		else:
			print(n + 1 - (int((n + 1) / 2 ** index) * 2 ** (index - 1) + k))
	else:
		for j in range(lx):
			if bx[j] != by[j]:
				index = lx - j
				if bx[j] == '0':
					flag = 0
				else:
					flag = 1
				break
		if (n + 1) % 2 ** index >= 2 ** (index - 1):
			k = 2 ** (index - 1)
		else:
			k = (n + 1) % 2 ** index
		if flag == 2:
			print(0)
		elif flag == 1:
			print(n + 1 - (int((n + 1) / 2 ** index) * 2 ** (index - 1) + k))
		else:
			print(int((n + 1) / 2 ** index) * 2 ** (index - 1) + k)


for _ in range(int(input())):
	(x, y, n) = list(map(int, input().split()))
	c = 0
	for i in range(n + 1):
		if x ^ i < y ^ i:
			c += 1
	print(c)


n = int(input())
for _ in range(n):
	(a, b, c) = [int(i) for i in input().split()]
	l = list(range(0, c + 1))
	d = 0
	for i in range(0, len(l)):
		if a ^ l[i] < b ^ l[i]:
			d = d + 1
	print(d)


testcases = int(input())
for testcase in range(testcases):
	temparr = input()
	temparr = temparr.split()
	x = int(temparr[0])
	y = int(temparr[1])
	n = int(temparr[2])
	if x == y:
		print(0)
		continue
	diffbit = 0
	biggestnum = 1 << 5
	checknum = 0
	flag = 0
	while True:
		curx = x & biggestnum
		cury = y & biggestnum
		if curx == cury:
			biggestnum = biggestnum >> 1
			continue
		checknum = biggestnum
		if curx:
			flag = 1
		break
	ans = 0
	for i in range(n + 1):
		if flag == 1:
			if i & checknum:
				ans += 1
		elif i & checknum == 0:
			ans += 1
	print(ans)


def XOR(x, y, n):
	c = 0
	for z in range(0, n + 1):
		a = x ^ z
		b = y ^ z
		if a < b:
			c += 1
	return c
T = int(input())
for t in range(T):
	(x, y, n) = map(int, input().split())
	result = XOR(x, y, n)
	print(result)


def setBitNumber(n):
	if n == 0:
		return -1
	msb = 0
	n = int(n / 2)
	while n > 0:
		n = int(n / 2)
		msb += 1
	return msb

def f(l, u, b):
	if u < 2 ** b:
		return 0
	mx = setBitNumber(u)
	ans = 0
	if b == mx:
		s = '0' + bin(u)[3:]
		return 1 + int(s, 2)
	ans += 2 ** (mx - 1)
	u -= 2 ** mx
	ans += f(l, u, b)
	return ans
t = int(input())
for i in range(t):
	(x, y, n) = map(int, input().split())
	x = bin(x)[2:]
	y = bin(y)[2:]
	while len(x) < len(y):
		x = '0' + x
	while len(y) < len(x):
		y = '0' + y
	c = -1
	for i in range(len(x)):
		if x[i] != y[i]:
			c = i
			tg = x[i]
			break
	if c == -1:
		print(0)
		continue
	c = len(x) - c - 1
	if tg == '1':
		print(f(0, n, c))
	else:
		print(n - f(0, n, c) + 1)


for _ in range(int(input())):
	(x, y, n) = map(int, input().split())
	z = x ^ 0 < y ^ 0
	q = 1
	while z == (x ^ q < y ^ q) and q < n + 1:
		q *= 2
	ans = (n + 1) // (q * 2) * q
	ans += min(q, n + 1 - ans * 2)
	print(ans if z else n + 1 - ans)


for t in range(int(input())):
	(x, y, n) = list(map(int, input().split()))
	count = 0
	for i in range(n + 1):
		if x ^ i < y ^ i:
			count += 1
	print(count)


a = int(input())
for i in range(a):
	b = list(map(int, str(input()).split(' ')))
	Ans = 0
	for i1 in range(b[2] + 1):
		if b[0] ^ i1 < b[1] ^ i1:
			Ans += 1
	print(Ans)


for _ in range(int(input())):
	(x, y, n) = list(map(int, input().split()))
	z = []
	count = 0
	for i in range(n + 1):
		z.append(i)
	for j in range(len(z)):
		if x ^ z[j] < y ^ z[j]:
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	(x, y, n) = list(map(int, input().split()))
	ct = 0
	for z in range(n + 1):
		if z ^ x < z ^ y:
			ct += 1
	print(ct)


from math import ceil

def leftset(n):
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n = n + 1
	return n >> 1
test = int(input())
for ____ in range(test):
	(x, y, n) = list(map(int, input().split()))
	if y < x:
		mask = leftset(x ^ y)
		remainder = (n + 1) % mask
		quo = (n + 1) // mask
		ans = mask * (quo // 2) + quo % 2 * remainder
		print(ans)
	elif x < y:
		mask = leftset(x ^ y)
		remainder = (n + 1) % mask
		quo = (n + 1) // mask
		ans = mask * ceil(quo / 2) + (quo + 1) % 2 * remainder
		print(ans)
	else:
		print(0)


for _ in range(int(input())):
	(x, y, n) = map(int, input().split())
	n += 1
	a = bin(x)[2:]
	a = '0' * (30 - len(a)) + a
	b = bin(y)[2:]
	b = '0' * (30 - len(b)) + b
	p = bin(n)[2:]
	p = '0' * (30 - len(p)) + p
	j = 0
	while j < 30:
		if a[j] != b[j]:
			break
		j += 1
	else:
		print(0)
		continue
	j = 29 - j
	res = 0
	curr = 2 ** 30
	for k in range(29, -1, -1):
		curr //= 2
		if p[29 - k] == '0':
			continue
		if k > j:
			res += curr // 2
		elif k == j:
			if a[29 - j] == '0':
				res += curr
		elif p[29 - j] == a[29 - j]:
			res += curr
	print(res)


for _ in range(int(input())):
	(x, y, n) = map(int, input().split())
	counter = 0
	for i in range(n + 1):
		if x ^ i < y ^ i:
			counter += 1
	print(counter)


def answer():
	if y == x:
		return 0
	(p1, p2) = (-1, -1)
	for i in range(30, -1, -1):
		if p2 == -1 and x >> i & 1 != y >> i & 1:
			p2 = i
		if p1 == -1 and n >> i & 1:
			p1 = i
	ans = n + 1
	if p1 >= p2:
		istheir = False
		for i in range(p1, -1, -1):
			if not istheir and i < p2:
				break
			if n >> i & 1:
				if i > p2:
					ans -= 1 << i - 1
				elif i < p2:
					ans -= 1 << i
				else:
					istheir = True
					ans -= 1
	return ans if y > x else n + 1 - ans
for T in range(int(input())):
	(x, y, n) = map(int, input().split())
	print(answer())


def optimized(x, y, n):
	if x == y:
		return 0
	p = (x ^ y).bit_length()
	diff = pow(2, p)
	n = n + 1
	ans = n // diff * (diff // 2)
	if x < y:
		return ans + (n % diff if n % diff < diff // 2 else diff // 2)
	else:
		return ans + (n % diff - diff // 2 if n % diff > diff // 2 else 0)
for test in range(int(input())):
	(x, y, n) = map(int, input().split())
	print(optimized(x, y, n))


for t in range(int(input())):
	(x, y, n) = map(int, input().split())
	n += 1
	count = 0
	flag = 0
	for i in range(28, -1, -1):
		if flag == 0:
			if x & 1 << i != y & 1 << i:
				for k in range(28, -1, -1):
					if n & 1 << k:
						if k > i:
							count += 1 << k - 1
						elif k == i:
							if x & 1 << i == 0:
								count += 1 << k
						elif x & 1 << i == n & 1 << i:
							count += 1 << k
				flag = 1
	print(count)


tc = int(input())
for j in range(tc):
	ip = list(map(int, input().rstrip().split()))
	x = ip[0]
	y = ip[1]
	n = ip[2]
	cnt = 0
	if x == y:
		print('0')
		continue
	ln = bin(x).replace('0b', '')
	rn = bin(y).replace('0b', '')
	ll = len(ln)
	rl = len(rn)
	if ll == len(rn):
		for i in range(ll):
			if ln[i] != rn[i]:
				ln = ln[i:]
				rn = rn[i:]
				break
	if ln[0] == '0':
		ln = ln[1:]
		ll -= 1
	if rn[0] == '0':
		rn = rn[1:]
		rl -= 1
	ll = len(ln)
	rl = len(rn)
	if ll > rl:
		lb = ll
	else:
		lb = rl
	pl = 2 ** lb
	hpl = pl // 2
	amn = (n + 1) // pl * hpl
	rm = (n + 1) % pl
	if rm * 2 <= pl:
		amn += rm
	else:
		amn += hpl
	aln = n + 1 - amn
	if x < y:
		print(amn)
	else:
		print(aln)


import math
N = int(input())
cases = []
for _ in range(int(N)):
	cases.append(list(map(lambda x: int(x), input().split(' '))))
for c in cases:
	(x, y, n) = c
	x = '{0:b}'.format(x)
	y = '{0:b}'.format(y)
	if len(x) > len(y):
		p = len(x) - 1
		f = True
	elif len(y) > len(x):
		p = len(y) - 1
		f = False
	else:
		for l in range(len(x)):
			if x[l] == '1' and y[l] == '0':
				p = len(x) - 1 - l
				f = True
				break
			elif y[l] == '1' and x[l] == '0':
				p = len(x) - 1 - l
				f = False
				break
		else:
			print(0)
			continue
	n += 1
	t = n // 2 ** (p + 1) * 2 ** p + min(2 ** p, n % 2 ** (p + 1))
	if not f:
		print(t)
	else:
		print(n - t)


for _ in range(int(input())):
	(x, y, n) = map(int, input().split())
	n += 1
	ans = 0
	are_same = True
	for j in range(29, -1, -1):
		if are_same:
			if x & 1 << j != y & 1 << j:
				for k in range(29, -1, -1):
					if j > k:
						if n & 1 << k:
							if n & 1 << j == x & 1 << j:
								ans += 1 << k
					elif j == k:
						if n & 1 << k:
							if x & 1 << j == 0:
								ans += 1 << k
					elif n & 1 << k:
						ans += 1 << k - 1
		if x & 1 << j != y & 1 << j:
			are_same = False
	print(ans)


tc = int(input())
for j in range(tc):
	ip = list(map(int, input().rstrip().split()))
	x = ip[0]
	y = ip[1]
	n = ip[2]
	cnt = 0
	for i in range(n + 1):
		if x ^ i < y ^ i:
			cnt += 1
	print(cnt)


testcases = int(input())
for testcase in range(testcases):
	temparr = input()
	temparr = temparr.split()
	x = int(temparr[0])
	y = int(temparr[1])
	n = int(temparr[2])
	if x == y:
		print(0)
		continue
	binaryx = '{0:b}'.format(x)
	binaryy = '{0:b}'.format(y)
	nx = len(binaryx)
	ny = len(binaryy)
	maxlen = max(nx, ny)
	binaryx = (maxlen - nx) * '0' + binaryx
	binaryy = (maxlen - ny) * '0' + binaryy
	binaryn = '{0:b}'.format(n)
	index = 0
	flag = 0
	for i in range(maxlen):
		if binaryx[i] == binaryy[i]:
			continue
		index = i
		if binaryy[i] == '0':
			flag = 1
			break
		break
	arr = []
	for i in range(maxlen):
		if i == index:
			arr.append('1')
		else:
			arr.append('0')
	newstrs = ''.join(arr)
	compareresult = int(newstrs, 2)
	ans = 0
	for i in range(n + 1):
		if flag == 1 and i & compareresult:
			ans += 1
		if flag == 0 and i & compareresult == 0:
			ans += 1
	print(ans)


for _ in range(int(input())):
	[x, y, n] = list(map(int, input().split()))
	if x == y:
		print(0)
	else:
		sn = bin(n)[2:]
		ln = len(sn)
		sx = bin(x)[2:]
		lx = len(sx)
		sy = bin(y)[2:]
		ly = len(sy)
		l = max(ln, lx, ly)
		sn = '0' * (l - ln) + sn
		sx = '0' * (l - lx) + sx
		sy = '0' * (l - ly) + sy
		for i in range(l):
			if sx[i] != sy[i]:
				break
		if i == 0:
			t1 = 1
		else:
			t1 = int(sn[:i], 2) + 1
		rstval = 2 ** (l - i - 1)
		if sx[i] == '0' and sn[i] == '1':
			print(t1 * rstval)
		elif sx[i] == '1' and sn[i] == '1':
			if i == l - 1:
				t2 = 1
			else:
				t2 = int(sn[i + 1:], 2) + 1
			print(t2 + (t1 - 1) * rstval)
		elif sx[i] == '1' and sn[i] == '0':
			t2 = rstval
			print((t1 - 1) * t2)
		else:
			if i == l - 1:
				t2 = 1
			else:
				t2 = int(sn[i + 1:], 2) + 1
			print(t2 + (t1 - 1) * rstval)


test = int(input())
for i in range(0, test):
	(x, y, n) = map(int, input().split())
	counter = 0
	for i in range(0, n + 1):
		n = x ^ i
		m = y ^ i
		if m > n:
			counter = counter + 1
	print(counter)


try:
	for _ in range(int(input())):
		(X, Y, N) = map(int, input().split())
		if X == Y:
			print(0)
		else:
			l = len(bin(X ^ Y)) - 3
			tmp = (N + 1) // pow(2, l)
			if X < Y:
				if tmp % 2 == 0:
					res = tmp // 2 * pow(2, l) + (N + 1) % pow(2, l)
				else:
					res = (tmp // 2 + tmp % 2) * pow(2, l)
			elif tmp % 2 == 0:
				res = tmp // 2 * pow(2, l)
			else:
				res = tmp // 2 * pow(2, l) + (N + 1) % pow(2, l)
			print(res)
except:
	pass


t = int(input())

def rounded(x):
	if x % 2 == 1:
		return x // 2 + 1
	else:
		return x // 2
for i in range(t):
	(x, y, z) = input().split()
	(x, y, z) = (int(x), int(y), int(z))
	count = 0
	inverted = False
	if x == y:
		print(0)
		continue
	if x > y:
		inverted = True
		(x, y) = (y, x)
	left = 0
	right = 1
	while x ^ right < y ^ right:
		right *= 2
	while left <= right:
		mid = left + (right - left) // 2
		if x ^ mid > y ^ mid:
			count = mid
			right = mid - 1
		else:
			left = mid + 1
	maxi = count
	jodi = (z + 1) // maxi
	bacha = (z + 1) % maxi
	bachahamara = (z + 1 - bacha) // maxi % 2 == 0
	count = rounded(jodi) * maxi
	if bachahamara:
		count += bacha
	if inverted:
		print(z + 1 - count)
	else:
		print(count)


def actual_string(x, y):
	if len(x) != len(y):
		return (x, y)
	elif x == y:
		return (x, y)
	else:
		while len(x) == len(y) and len(x) != 1:
			if x[0] == y[0]:
				x = x[1:]
				y = y[1:]
			elif x[0] == '0':
				x = x[1:]
			else:
				y = y[1:]
		return (x, y)
for _ in range(int(input())):
	(x, y, n) = input().split()
	(x, y, n) = (int(x), int(y), int(n))
	(x, y) = (bin(x), bin(y))
	x = x[2:]
	y = y[2:]
	(x, y) = actual_string(x, y)
	x = int(x)
	y = int(y)
	x = str(x)
	y = str(y)
	len_of_x = len(x)
	len_of_y = len(y)
	x = int(x, 2)
	y = int(y, 2)
	summ = 0
	count_storer = 0
	complete = 0
	if x == y:
		summ = 0
	elif n == 0:
		if x < y:
			summ = 1
		else:
			summ = 0
	elif len_of_x < len_of_y or (x == 0 and y == 1):
		count_storer += 2 ** (len_of_y - 1) - 1
		if n >= count_storer:
			summ += 2 ** (len_of_y - 1)
		else:
			summ += n + 1
			complete = 1
		count_storer = 2 ** len_of_y - 1
		if complete == 0 and n <= count_storer:
			complete = 1
		if complete == 0:
			n -= count_storer
			divisor = n // 2 ** (len_of_y - 1)
			reminder = n % 2 ** (len_of_y - 1)
			if divisor % 2 == 0:
				summ += divisor // 2 * 2 ** (len_of_y - 1) + reminder
			else:
				summ += (divisor // 2 + 1) * 2 ** (len_of_y - 1)
	else:
		count_storer += 2 ** (len_of_x - 1) - 1
		if n <= count_storer:
			summ = 0
			complete = 1
		count_storer = 2 ** len_of_x - 1
		if complete == 0 and n <= count_storer:
			summ += n - 2 ** (len_of_x - 1) + 1
			complete = 1
		elif complete == 0:
			summ += 2 ** (len_of_x - 1)
		if complete == 0:
			n -= count_storer
			divisor = n // 2 ** (len_of_x - 1)
			reminder = n % 2 ** (len_of_x - 1)
			if divisor % 2 == 0:
				summ += divisor // 2 * 2 ** (len_of_x - 1)
			else:
				summ += divisor // 2 * 2 ** (len_of_x - 1) + reminder
	print(summ)


from random import randint
f = input

def din(st):
	return bin(st)[2:].zfill(10)

def func(x, y, n):
	z0 = x ^ 0 < y ^ 0
	unmatch = 1
	while z0 == (x ^ unmatch < y ^ unmatch) and unmatch < n + 1:
		unmatch *= 2
	ans = (n + 1) // (unmatch * 2) * unmatch
	ans += min(unmatch, n + 1 - ans * 2)
	return ans if z0 else n + 1 - ans
for _ in range(int(f())):
	(x, y, n) = map(int, f().split())
	print(func(x, y, n))


import math
import bisect
read = lambda : list(map(int, input().strip().split()))
rs = lambda : int(input().strip())
t = rs()
ans = []

def find(x, y, n):
	d = x ^ y
	if d == 0:
		return 0
	msb = None
	for i in range(30, -1, -1):
		if d >> i > 0:
			msb = i
			break
	t = n + 1
	num = t >> msb + 1
	num = num << msb
	num += max(0, t % (1 << msb + 1) - (1 << msb))
	if y & 1 << msb:
		return t - num
	return num
for _ in range(t):
	(xc, yc, nc) = read()
	ans.append(find(xc, yc, nc))
print('\n'.join([str(x) for x in ans]))


for _ in range(int(input())):
	(x, y, n) = map(int, input().split())
	n += 1
	ans = 0
	for i in range(29, -1, -1):
		if x & 1 << i != y & 1 << i:
			for k in range(29, -1, -1):
				if n & 1 << k > 0:
					if k > i:
						ans += 1 << k - 1
					elif k == i:
						if x & 1 << i == 0:
							ans += 1 << k
					elif n & 1 << i == x & 1 << i:
						ans += 1 << k
			break
	print(ans)


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
t = int(input())
for i in range(t):
	(x, y, n) = map(int, input().split())
	if x == y:
		print(0)
		continue
	elif n == 0:
		if x < y:
			print(1)
		else:
			print(0)
		continue
	l = int(math.log2(n))
	b = int(math.log2(x ^ y))
	if b > l:
		if x > y:
			print(0)
		else:
			print(n + 1)
		continue
	ans = 0
	for j in range(l, b, -1):
		if n & 1 << j:
			ans += pow(2, j - 1)
	if x > y:
		if n & 1 << b:
			for j in range(b - 1, -1, -1):
				if n & 1 << j:
					ans += pow(2, j)
			ans += 1
	elif n & 1 << b:
		ans += pow(2, b)
	else:
		for j in range(b - 1, -1, -1):
			if n & 1 << j:
				ans += pow(2, j)
		ans += 1
	print(ans)


from math import log as l
for _ in range(int(input())):
	(x, y, n) = map(int, input().split())
	if n < 64:
		c = 0
		for z in range(n + 1):
			if x ^ z < y ^ z:
				c += 1
		print(c)
	else:
		ab = x ^ y
		if x == y:
			print(0)
		elif x > y:
			r = 2 ** int(l(ab, 2))
			c = 0
			st = r
			if st > n:
				print(0)
			elif n >= st and n <= 2 * r - 1:
				print(n - st + 1)
			else:
				while True:
					c += r
					st += 2 * r
					check = st + r - 1
					if n >= st and n <= check:
						c += n - st + 1
						break
					if st > n:
						break
				print(c)
		else:
			r = 2 ** int(l(ab, 2))
			c = 0
			st = 0
			if n >= st and n <= r:
				print(n + 1)
			else:
				while True:
					c += r
					st += 2 * r
					check = st + r - 1
					if n >= st and n <= check:
						c += n - st + 1
						break
					if st > n:
						break
				print(c)


for _ in range(int(input())):
	c = 0
	(x, y, n) = tuple(map(int, input().split()))
	for z in range(0, n + 1):
		if x ^ z < y ^ z:
			c += 1
	print(c)


def solve(x, y, n):
	z = x ^ 0 < y ^ 0
	pos_z = 1
	while z == (x ^ pos_z < y ^ pos_z) and pos_z < n + 1:
		pos_z *= 2
	ans = (n + 1) // (pos_z * 2) * pos_z
	ans += min(pos_z, n + 1 - ans * 2)
	return ans if z else n + 1 - ans
for _ in range(int(input())):
	(x, y, n) = map(int, input().split())
	print(solve(x, y, n))


t = int(input())
for gg in range(t):
	l = list(map(int, input().strip().split()))
	x = l[0]
	y = l[1]
	n = l[2] + 1
	z1 = bin(x)
	z1 = z1[2:]
	c1 = z1.zfill(30)
	z2 = bin(y)
	z2 = z2[2:]
	c2 = z2.zfill(30)
	if x == y:
		print(0)
	elif x < y:
		for i in range(30):
			if c1[i] != c2[i]:
				siz = 30 - i
				break
		size = 2 ** (siz - 1)
		t = n // size
		imp = n % size
		if t % 2 == 0:
			print(size * (t // 2) + imp)
		else:
			print(size * (t // 2 + 1))
	else:
		for i in range(30):
			if c1[i] != c2[i]:
				siz = 30 - i
				break
		size = 2 ** (siz - 1)
		t = n // size
		imp = n % size
		if t % 2 == 0:
			print(size * (t // 2))
		else:
			print(size * (t // 2) + imp)