JJ has three integers A, B, and N. He can apply the following operation on A: 
Select an integer X such that 1 ≤ X < N and set A := A \oplus X. (Here, \oplus denotes the [bitwise XOR operation].)

JJ wants to make A equal to B.  
Determine the minimum number of operations required to do so. Print -1 if it is not possible.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains three integers A, B, and N — the parameters mentioned in the statement.

------ Output Format ------ 

For each test case, output the minimum number of operations required to make A equal to B. Output -1 if it is not possible to do so. 

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$0 ≤ A, B < 2^{30}$
$1 ≤ N ≤2^{30}$

------ subtasks ------ 

Subtask 1 (30 points): $N$ is a power of $2$.
Subtask 2 (70 points): Original Constraints.

----- Sample Input 1 ------ 
3
5 5 2
3 7 8
8 11 1

----- Sample Output 1 ------ 
0
1
-1

----- explanation 1 ------ 
- Test Case $1$: $A$ is already equal to $B$. Hence we do not need to perform any operation.
- Test Case $2$: We can perform the operation with $X = 4$ which is $< 8$. Therefore $A = 3 \oplus 4 = 7$. Thus, only one operation is required.
- Test Case $3$: We can show that it is not possible to make $A$ equal to $B$.

----- Sample Input 2 ------ 
2
24 27 3
4 5 1000

----- Sample Output 2 ------ 
2
1
----- explanation 2 ------ 
Note that the above sample case belongs to subtask $2$.

- Test Case 1: We can first perform the operation with $X = 1$ which is $< 3$. Therefore $A = 24 \oplus 1 = 25$. Then we can perform the operation with $X = 2$ which is $< 3$. Therefore $A = 25 \oplus 2 = 27$. Therefore we can make $A$ equal to $B$ in $2$ operations. It can be shown that it is not possible to do this in less than $2$ operations.

Difficulty: MEDIUM
Tags: Bit manipulation

Mathematics

Greedy algorithms
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
for i in range(int(input())):
	(a, b, n) = map(int, input().split())
	n -= 1
	diff = a ^ b
	bits = len(bin(diff)[2:])
	pwr = pow(2, bits - 1)
	if a == b:
		print(0)
	elif diff <= n:
		print(1)
	elif pwr <= n:
		print(2)
	else:
		print(-1)


t = int(input())

def fun(a, b, n):
	diff = bin(b ^ a)[2:]
	pr = pow(2, len(diff) - 1)
	if n >= pr:
		vl = a ^ b
		if vl <= n:
			return 1
		else:
			return 2
	else:
		return -1
for _ in range(t):
	(a, b, n) = map(int, input().split())
	dif = b - a
	if dif == 0:
		print(0)
	else:
		x = fun(a, b, n - 1)
		print(x)


import math
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	k = a ^ b
	if k != 0:
		c = int(math.log(k, 2))
		s = int(pow(2, c))
	if a == b:
		print(0)
	elif n > k:
		print(1)
	elif n > s and n <= k:
		print(2)
	else:
		print(-1)


def sz(n):
	if n == 0:
		return -1
	else:
		count = 0
		while n != 1:
			count += 1
			n = int(n / 2)
		return count
for _ in range(int(input())):
	(A, B, N) = [int(x) for x in input().split()]
	if A == 0 and B == 0:
		print(0)
		continue
	sza = sz(A) + 1
	szb = sz(B) + 1
	mx = max(sza, szb)
	a = [0 for _ in range(mx)]
	for i in reversed(range(sza)):
		if A - pow(2, i) >= 0:
			a[i] = 1
			A -= pow(2, i)
	b = [0 for _ in range(mx)]
	for i in reversed(range(szb)):
		if B - pow(2, i) >= 0:
			b[i] = 1
			B -= pow(2, i)
	(mx1, sm) = (-1, 0)
	for i in range(mx):
		if a[i] != b[i]:
			sm += pow(2, i)
			mx1 = i
	if mx1 == -1:
		print(0)
	elif N <= pow(2, mx1):
		print(-1)
	elif N > pow(2, mx1) and N <= sm:
		print(2)
	else:
		print(1)


import math
t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	if a == b:
		print(0)
	else:
		d = a ^ b
		m = math.floor(math.log(d, 2))
		m = pow(2, m)
		if m >= c:
			print(-1)
		elif c > d:
			print(1)
		else:
			print(2)


import math
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	x = a ^ b
	n -= 1
	if x == 0:
		print(0)
	elif x <= n:
		print(1)
	elif n > 0 and int(math.log2(x)) == int(math.log2(n)):
		print(2)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(0)
		continue
	val = a ^ b
	if val < n:
		print(1)
		continue
	while val >= n:
		val = val - (val & -val)
	if val:
		print(2)
	else:
		print(-1)


import math
tc = int(input().strip())
for t in range(tc):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(0)
	else:
		x = a ^ b
		if x < n:
			print(1)
		else:
			while x >= n:
				x -= x & -x
			if x:
				print(2)
			else:
				print(-1)


n = int(input())
while n:
	n -= 1
	(a, b, N) = map(int, input().split())
	if a == b:
		print(0)
		continue
	x = a ^ b
	b = len(bin(x)[2:]) - 1
	if x < N:
		print(1)
	elif N <= x and N >= 2 ** b + 1:
		print(2)
	else:
		print(-1)


import math
for _ in range(int(input())):
	(A, B, N) = map(int, input().split())
	X = A ^ B
	N -= 1
	if X == 0:
		print(0)
	elif X <= N:
		print(1)
	elif N > 0 and int(math.log2(X)) == int(math.log2(N)):
		print(2)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(0)
		continue
	t = a ^ b
	b = len(bin(t)[2:]) - 1
	if n > t:
		print(1)
	elif n <= t and n >= 2 ** b + 1:
		print(2)
	else:
		print('-1')


T = int(input())
for x in range(T):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(0)
		continue
	v = a ^ b
	if v < n:
		print(1)
		continue
	while v >= n:
		v = v - (v & -v)
	if v:
		print(2)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	p = a ^ b
	if p == 0:
		print(0)
	elif p < n:
		print(1)
	elif 2 ** (len(bin(p)) - 3) < n:
		print(2)
	else:
		print(-1)


def solve(a, b, n):
	if a == b:
		print(0)
		return
	x = a ^ b
	if x < n:
		print(1)
	elif 2 ** (len(bin(x)) - 3) < n:
		print(2)
	else:
		print(-1)
t = int(input())
for _ in range(t):
	(a, b, n) = list(map(int, input().split()))
	solve(a, b, n)


for q in range(int(input())):
	(a, b, n) = [int(x) for x in input().split()]
	if a == b:
		print(0)
		continue
	x = a ^ b
	if x < n:
		print(1)
	elif 2 ** (len(bin(x)) - 3) < n:
		print(2)
	else:
		print(-1)


def op(a, b, n):
	arra = [0 for i in range(30)]
	arrb = [0 for i in range(30)]
	j = 29
	while a > 0 or b > 0:
		arra[j] = a & 1
		arrb[j] = b & 1
		a >>= 1
		b >>= 1
		j -= 1
	j = 29
	val = 0
	res = 0
	countbits = 0
	while j >= 0:
		if arra[j] == arrb[j]:
			val += pow(2, 29 - j) * 0
		else:
			val += pow(2, 29 - j) * 1
			countbits += 1
		if val >= n:
			if countbits > 1:
				res += 1
				countbits = 0
				val = 0
				continue
			else:
				return -1
		j -= 1
	if countbits > 0 and val < n:
		res += 1
	return res
case = int(input())
for i in range(case):
	(a, b, n) = map(int, input().split(' '))
	ans = op(a, b, n)
	print(ans)


import math
tests = int(input())
for i in range(tests):
	(a, b, n) = map(int, input().split())
	required = a ^ b
	if required == 0:
		print(0)
	elif n - 1 <= 0 or math.floor(math.log(required, 2)) > math.floor(math.log(n - 1, 2)):
		print(-1)
	elif n > required:
		print(1)
	else:
		print(2)


from math import log
for _ in range(int(input())):
	(a, b, n) = map(int, input().split(' '))
	x = a ^ b
	if a ^ b == 0:
		print(0)
		continue
	if a ^ b < n:
		print(1)
	elif int(log(x, 2)) == int(log(n, 2)):
		if n & n - 1:
			print(2)
		else:
			print(-1)
	else:
		print(-1)


from math import log, pow
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	c = a ^ b
	if c == 0:
		print(0)
	elif c < n:
		print(1)
	elif pow(2, int(log(c, 2))) < n:
		print(2)
	else:
		print(-1)


for i in range(int(input())):
	(a, b, n) = map(int, input().split())
	x = a ^ b
	if x == 0:
		print(0)
	elif x < n:
		print(1)
	elif x > 1 and len(bin(x)) == len(bin(n - 1)):
		print(2)
	else:
		print(-1)


T = int(input())

def check(N):
	l = len(bin(N)) - 2
	temp = 2 ** (l - 1)
	if temp == N:
		return False
	return True
for i in range(0, T):
	(A, B, N) = map(int, input().split())
	C = A ^ B
	if A == B:
		print(0)
	elif C < N:
		print(1)
	elif C > N and len(bin(C)) == len(bin(N)) and check(N):
		print(2)
	elif C == N:
		if check(N):
			print(2)
		else:
			print(-1)
	else:
		print(-1)


import math
for i in range(int(input())):
	(a, b, n) = map(int, input().split())
	res = a ^ b
	if res == 0:
		print(0)
	elif res < n:
		print(1)
	elif res > 1 and len(bin(res)) == len(bin(n - 1)):
		print(2)
	else:
		print(-1)


def countbit(n):
	count = 0
	while n > 0:
		n >>= 1
		count += 1
	return count
T = int(input())
while T > 0:
	(a, b, n) = map(int, input().split())
	t = a ^ b
	if t == 0:
		print(0)
	elif 0 < t < n:
		print(1)
	elif countbit(t) == countbit(n - 1):
		print(2)
	else:
		print(-1)
	T -= 1


from bisect import bisect_left
from code import interact
from heapq import heapify, heappush, heappop
from collections import deque
from pydoc import plain
from re import X
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	(a, b, n) = il()
	a = bin(a)[2:]
	b = bin(b)[2:]
	if len(a) > len(b):
		b = '0' * (len(a) - len(b)) + b
	if len(b) > len(a):
		a = '0' * (len(b) - len(a)) + a
	cost = 0
	flag = True
	for i in range(len(a)):
		if a[i] != b[i]:
			if 2 ** (len(a) - i - 1) > n - 1:
				print(-1)
				flag = False
				break
			else:
				cost += 2 ** (len(a) - i - 1)
	if flag:
		if cost == 0:
			print(0)
		elif cost <= n - 1:
			print(1)
		else:
			print(2)


def function(A, B, N):
	if A == B:
		return 0
	val = A ^ B
	if val < N:
		return 1
	else:
		c1 = 0
		c2 = 0
		N = N - 1
		while val:
			if N:
				c1 += 1
				N = N >> 1
			c2 += 1
			val = val >> 1
		if c1 == c2:
			return 2
		else:
			return -1

def main():
	T = int(input())
	for _ in range(T):
		(A, B, N) = list(map(int, input().split(' ')))
		val = function(A, B, N)
		print(val)
main()


def answer(a, b, n):
	if a == b:
		return 0
	xor = a ^ b
	if xor < n:
		return 1
	z = 1
	while z < n:
		z *= 2
	if xor < z:
		return 2
	return -1
for T in range(int(input())):
	(a, b, n) = map(int, input().split())
	print(answer(a, b, n))


import math
for _ in range(int(input())):
	(x, y, n) = map(int, input().split())
	c = x ^ y
	z = 1
	while z < n:
		z *= 2
	if c == 0:
		print(0)
	elif c < n:
		print(1)
	elif c < z:
		print(2)
	else:
		print(-1)


t = int(input())
while t:
	li = [int(x) for x in input().split()]
	a = li[0]
	b = li[1]
	n = li[2]
	c = a ^ b
	z = 1
	while z < n:
		z *= 2
	if c == 0:
		print(0)
	elif c < n:
		print(1)
	elif c < z:
		print(2)
	else:
		print(-1)
	t -= 1


import math
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	c = a ^ b
	z = 1
	while z < n:
		z *= 2
	if c == 0:
		print(0)
	elif c < n:
		print(1)
	elif c < z:
		print(2)
	else:
		print(-1)


for _ in range(int(input())):
	(A, B, N) = map(int, input().split())
	X = A ^ B
	if X == 0:
		print(0)
	elif 1 <= X < N:
		print(1)
	elif N != 1 and len(str(bin(X))) == len(str(bin(N - 1))):
		print(2)
	else:
		print(-1)


for t in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(0)
		continue
	(bina, binb) = (bin(a)[:1:-1], bin(b)[:1:-1])
	(la, lb) = (len(bina), len(binb))
	diff = ''
	for i in range(min(la, lb)):
		if bina[i] == binb[i]:
			diff += '0'
		else:
			diff += '1'
	if la > lb:
		diff += bina[lb:]
	if la < lb:
		diff += binb[la:]
	diff = diff[::-1].lstrip('0')
	if int(diff, 2) < n:
		print(1)
		continue
	newdiff = diff[0] + '0' * (len(diff) - 1)
	if int(newdiff, 2) < n:
		print(2)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	x = a ^ b
	z = 1
	while z < c:
		z *= 2
	if x == 0:
		print(0)
	elif x < c:
		print(1)
	elif x < z:
		print(2)
	else:
		print(-1)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	z = 1
	while z < n:
		z *= 2
	if a == b:
		print(0)
	elif a ^ b < n:
		print(1)
	elif a ^ b < z:
		print(2)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b, n) = (int(i) for i in input().split())
	c = a ^ b
	if a == b:
		print(0)
		continue
	if c < n:
		print(1)
	elif 2 ** (len(bin(c)) - 3) < n:
		print(2)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b, n) = list(map(int, input().split()))
	s = 1
	while s < n:
		s *= 2
	if a == b:
		print(0)
	elif a ^ b < n:
		print(1)
	elif a ^ b < s:
		print(2)
	else:
		print(-1)


import math
for _ in range(int(input())):
	lis = list(map(int, input().split()))
	s = bin(lis[0]).replace('0b', '')
	t = bin(lis[1]).replace('0b', '')
	n = lis[2]
	c = 0
	s = s[::-1]
	t = t[::-1]
	l1 = [0] * 32
	l2 = [0] * 32
	for i in range(len(s)):
		if s[i] == '1':
			l1[i] = 1
	for i in range(len(t)):
		if t[i] == '1':
			l2[i] = 1
	l3 = []
	k = True
	for i in range(32):
		if l1[i] != l2[i]:
			if math.pow(2, i) >= n:
				k = False
			else:
				l3.append(int(math.pow(2, i)))
	i = 0
	if k == True:
		c = 0
		while i < len(l3):
			ss = 0
			j = i
			while j < len(l3) and ss + l3[j] < n:
				ss += l3[j]
				j += 1
			ss = 0
			c += 1
			i = j
		print(c)
	else:
		print(-1)


ans = []
for _ in range(int(input())):
	(A, B, N) = [int(x) for x in input().split()]
	AexorB = A ^ B
	(binAexorB, binN) = (bin(AexorB)[2:], bin(N - 1)[2:])
	if A == B:
		an = 0
	elif AexorB < N:
		an = 1
	elif N != 1 and len(binAexorB) == len(binN):
		an = 2
	else:
		an = -1
	ans.append(an)
print(*ans, sep='\n')


t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(0)
	else:
		z = 1
		while z < n:
			z *= 2
		if a ^ b < n:
			print(1)
		elif a ^ b < z:
			print(2)
		else:
			print(-1)


t = int(input())
for i in range(0, t):
	abn = input()
	abn = abn.split(' ')
	a = int(abn[0])
	b = int(abn[1])
	n = int(abn[2])
	ai = bin(a)
	ai = ai.replace('0b', '')
	bi = bin(b)
	bi = bi.replace('0b', '')
	mi = bin(n - 1)
	mi = mi.replace('0b', '')
	l = max(len(ai), len(bi), len(mi))
	ai = (l - len(ai)) * '0' + ai
	bi = (l - len(bi)) * '0' + bi
	mi = (l - len(mi)) * '0' + mi
	x = ''
	for i2 in range(0, l):
		k = int(str(ai)[i2]) ^ int(str(bi)[i2])
		x = x + str(k)
	tr = 0
	for i3 in range(0, l):
		k2 = (mi[i3], x[i3])
		if a == b:
			tr = 0
			break
		if k2 == ('0', '0'):
			continue
		if k2 == ('1', '0'):
			tr = 1
			break
		if k2 == ('1', '1'):
			tr = 1
			continue
		if k2 == ('0', '1'):
			if tr == 0:
				tr = -1
				break
			else:
				tr = 2
				break
	print(tr)


t = int(input())

def fun(a, b, n):
	if a == b:
		return 0
	x = a ^ b
	if x < n:
		return 1
	c = 0
	while x > 0:
		x = x >> 1
		c = c + 1
	if 2 ** (c - 1) < n:
		return 2
	return -1
while t > 0:
	(a, b, n) = [int(i) for i in input().split()]
	print(fun(a, b, n))
	t = t - 1


from math import log2
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(0)
		continue
	req = 0
	for i in range(30):
		if a & 1 << i != b & 1 << i:
			req += 1 << i
	if req < n:
		print(1)
	elif 1 << int(log2(req)) < n:
		print(2)
	else:
		print(-1)


ans = ''
for _ in range(int(input())):
	(a, b, n) = list(map(int, input().split()))
	count = 0
	poss = True
	if a == b:
		count = 0
	elif a ^ b < n:
		count = 1
	else:
		for i in range(31, -1, -1):
			if (a ^ b) & 1 << i >= n:
				poss = False
				break
		if not poss:
			ans += '-1\n'
			continue
		else:
			count = 2
	ans += str(count) + '\n'
print(ans)


from math import log, floor
test = int(input())
while test:
	(a, b, n) = map(int, input().split())
	n -= 1
	if a == b:
		print(0)
	elif a ^ b <= n:
		print(1)
	elif n != 0 and floor(log(a ^ b, 2)) == floor(log(n, 2)):
		print(2)
	else:
		print(-1)
	test -= 1


import math
t = int(input())
for _ in range(t):
	(a, b, n) = map(int, input().split())
	if a == b:
		print(0)
		continue
	x = a ^ b
	z = 1
	while z < n:
		z *= 2
	if x == 0:
		print(0)
	elif x < n:
		print(1)
	elif x < z:
		print(2)
	else:
		print(-1)


t = int(input())
for i in range(t):
	li = list(map(int, input().split()))
	a = li[0]
	b = li[1]
	n = li[2]
	n -= 1
	if a == b:
		print(0)
		continue
	q = a ^ b
	temp = q
	res = 0
	while temp:
		if res:
			res *= 2
		else:
			res = 1
		temp = temp >> 1
	if n < res:
		print(-1)
	elif n >= q:
		print(1)
	else:
		print(2)


import math
for _ in range(int(input())):
	(x, y, N) = map(int, input().split())
	d = x ^ y
	if d == 0:
		print(0)
	elif d in range(1, N):
		print(1)
	elif 2 ** (len(bin(d)) - 3) >= N:
		print(-1)
	else:
		print(2)


t = int(input())
while t:
	(a, b, n) = map(int, input().split(' '))
	num = 0
	count = 0
	flag = False
	for i in range(29, -1, -1):
		val = 1 << i
		if a & val and (not b & val):
			if val >= n:
				print(-1)
				break
			else:
				if num + val >= n:
					count += 1
					a ^= num
					num = val
				else:
					num += val
				flag = True
	else:
		for i in range(30):
			val = 1 << i
			if b & val and (not a & val):
				if val >= n:
					print(-1)
					break
				elif num + val >= n:
					count += 1
					a ^= num
					num = val
				else:
					num += val
				flag = True
		else:
			if flag:
				count += 1
			print(count)
	t -= 1


T = int(input())

def algo():
	(x, y, N) = map(int, input().split())
	d = x ^ y
	if d == 0:
		print(0)
	elif d in range(1, N):
		print(1)
	elif 2 ** (len(bin(d)) - 3) >= N:
		print(-1)
	else:
		print(2)
for i in range(T):
	algo()