Chef has two integers X and S. He is interested in sequences of non-negative integers such that the sum of their elements is S and the [bitwise OR] of their elements is X. Chef would like to know the shortest possible length such a sequence can have.

Formally, find the smallest positive integer N such that there exists a sequence A = [A_{1}, A_{2}, \ldots, A_{N}] satisfying the following conditions:
Each A_{i} is a non-negative integer
A_{1} + A_{2} + \ldots + A_{N} = S
A_{1} \vee A_{2} \vee \ldots \vee A_{N} = X

where \vee denotes the bitwise OR operation.

If there does not exist any sequence which satisfies the above conditions, output -1. Otherwise, output the minimum possible length of such a sequence.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input, containing two space-separated integers X and S — the required bitwise OR and sum, respectively.

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

For each test case, output a single line containing one integer — the shortest possible length of such a sequence, or -1 if no such sequence exists.

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

$1 ≤ T ≤ 1000$
$1 ≤ X ≤ S ≤ 10^{9}$

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

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
13 23
6 13
1 25

----- Sample Output 1 ------ 
3
-1
25

----- explanation 1 ------ 
Test Case $1$: One of the valid arrays of length $3$ is $[9,9,5]$. It can be shown that there is no valid array with length $< 3$.

Test Case $2$: There does not exist any sequence whose sum is $13$ and bitwise OR is $6$.

Test Case $3$: The valid array of minimum length contains $25$ ones.

Difficulty: VERY_HARD

Starter code:

Solutions:
def binarize(num):
	powers = []
	power = 0
	while num > 0:
		bit = num % 2
		num = num // 2
		if bit:
			powers.append(power)
		power += 1
	return list(reversed(powers))

def doit(x, s):
	if s < x:
		return -1
	origs = s
	repeats = 1
	s = s - x
	origs = s
	binx = binarize(x)
	mintimes = 0
	for power in binx:
		val = 2 ** power
		times = s // val
		s = s % val
		mintimes = max(mintimes, times)
	if s != 0:
		return -1
	return optimize(binx, origs, -1, mintimes) + repeats

def possible(binx, s, mpw):
	for power in binx:
		val = 2 ** power
		times = min(s // val, mpw)
		s = s - val * times
	if s != 0:
		return 0
	return 1

def optimize(binx, s, mn, mx):
	mid = (mn + mx) // 2
	if mid == mn:
		return mx
	if possible(binx, s, mid):
		return optimize(binx, s, mn, mid)
	else:
		return optimize(binx, s, mid, mx)
t = int(input())
for tt in range(t):
	(x, s) = [int(xx) for xx in input().split(' ')]
	print(str(doit(x, s)))


def ok(m, x, s):
	ns = s - x
	for msb in bits:
		if ns >= msb:
			q = min(m - 1, ns // msb)
			ns -= q * msb
	return ns == 0
t = int(input())
for i in range(t):
	(x, s) = map(int, input().split())
	bits = []
	for i in range(30, -1, -1):
		if x >> i & 1:
			num = 1 << i
			bits.append(num)
	l = 1
	r = s
	ans = -1
	while l <= r:
		m = (l + r) // 2
		if ok(m, x, s):
			ans = m
			r = m - 1
		else:
			l = m + 1
	print(ans)


import sys
from functools import reduce
import math

def is_possible(cap, bit_idx, target):
	if cap >= target:
		return True
	elif cap == 0:
		return False
	for b in bit_idx:
		m = min(cap, target // 2 ** b)
		target -= m * 2 ** b
		if target == 0:
			return True
	return False

def binary_search(f, low, high):
	mid = (high + low) // 2
	if high <= low:
		return low
	if f(mid):
		return binary_search(f, low, mid)
	else:
		return binary_search(f, mid + 1, high)

def get_bit_idx(x):
	bits = []
	idx = 0
	while 2 ** idx <= x:
		if x >> idx & 1:
			bits.append(idx)
		idx += 1
	return bits

def solve(X, S):
	t = S - X
	n = 1
	bi = get_bit_idx(X)[::-1]
	if t % 2 ** bi[-1] > 0:
		return -1
	t //= 2 ** bi[-1]
	bi = [b - bi[-1] for b in bi]
	return binary_search(lambda cap: is_possible(cap, bit_idx=bi, target=t), 0, t) + 1

def pp(input):
	cases = int(input())
	for case in range(cases):
		(X, S) = map(int, input().split())
		print(solve(X, S))
lines = iter(sys.stdin.read().split('\n'))
pp(lambda : next(lines))


def possible(X, S, count):
	sum = S - X
	count -= 1
	B = 29
	for b in range(B, -1, -1):
		if X >> b & 1 == 0:
			continue
		times = min(count, sum // 2 ** b)
		sum -= times * 2 ** b
	return sum == 0

def solve():
	for _ in range(int(input())):
		(x, s) = list(map(int, input().split()))
		l = 1
		r = 10 ** 9 + 1
		while l < r:
			m = int(l + (r - l) / 2)
			if possible(x, s, m):
				r = m
			else:
				l = m + 1
		if r > 10 ** 9:
			r = -1
		print(r)
solve()


for _ in range(int(input())):
	(x, s) = map(int, input().split())
	(cnt, i, l, h) = ([], 0, 1, 10 ** 9 + 1)
	while 1 << i <= x:
		if 1 << i & x > 0:
			cnt.append(1 << i)
		i += 1
	while l < h:
		mid = (l + h) // 2
		suma = s - x
		for j in range(len(cnt) - 1, -1, -1):
			suma -= min(mid - 1, suma // cnt[j]) * cnt[j]
		if suma == 0:
			h = mid
		else:
			l = mid + 1
	if h < 10 ** 9 + 1:
		print(h)
	else:
		print(-1)


def possible(x, s, cnt):
	total = s - x
	cnt -= 1
	bit = 29
	for i in range(bit, -1, -1):
		if x & 1 << i == 0:
			continue
		else:
			time = min(cnt, total // (1 << i))
			total -= time * (1 << i)
	return total == 0
for _ in range(int(input())):
	(x, s) = map(int, input().split())
	low = 1
	high = 10 ** 9 + 1
	while low < high:
		mid = low + (high - low) // 2
		if possible(x, s, mid):
			high = mid
		else:
			low = mid + 1
	if high > 10 ** 9:
		print('-1')
	else:
		print(high)


def check(size):
	S = s - x
	size -= 1
	for j in range(29, -1, -1):
		if x & 1 << j:
			times = min(size, S // (1 << j))
			S -= times * (1 << j)
	return S == 0
for _ in range(int(input())):
	(x, s) = map(int, input().split())
	l = 1
	high = 10 ** 9 + 1
	ans = -1
	while l <= high:
		mid = (l + high) // 2
		if check(mid):
			ans = mid
			high = mid - 1
		else:
			l = mid + 1
	print(ans)


bits = [pow(2, i) for i in range(30, -1, -1)]

def gen(m, coins, target):
	for coin in coins:
		target -= coin * min(m, target // coin)
	return target == 0

def getArr(x):
	ans = []
	for b in bits:
		if x >= b:
			x -= b
			ans.append(b)
	return ans

def isInvalid(x, s):
	if x > s:
		return True
	while x % 2 == 0 and x > 0:
		if s % 2 == 1:
			return True
		x = x // 2
		s = s // 2
	return False

def mysol(x, s):
	if x == 0:
		return -1
	if isInvalid(x, s):
		return -1
	s -= x
	low = s // x
	high = s
	xrr = getArr(x)
	while low < high:
		mid = (low + high) // 2
		if gen(mid, xrr, s):
			high = mid
		else:
			low = mid + 1
	return 1 + high
for _ in range(int(input())):
	(x, s) = map(int, input().split())
	print(mysol(x, s))


def BS(B, S, N, X):
	S -= X
	newN = int(N - 1)
	for i in range(len(B) - 1, -1, -1):
		if B[i] == '1':
			count = S // 2 ** i
			S -= min(newN, count) * 2 ** i
	return S == 0
for t in range(int(input())):
	(X, S) = map(int, input().split())
	if X > S:
		print(-1)
		continue
	B = str(bin(X))[2:]
	B = B[::-1]
	l = 1
	r = int(S)
	while r != l:
		mid = (r + l) // 2
		newS = int(S)
		if BS(B, newS, mid, X):
			r = int(mid)
		else:
			l = int(mid + 1)
	if BS(B, S, l, X):
		print(l)
	else:
		print(-1)


from sys import stdin
input = stdin.readline

def check(size):
	req = s - x
	for i in range(29, -1, -1):
		if x >> i & 1:
			remove = size * (1 << i)
			if remove <= req:
				req -= remove
			else:
				req %= 1 << i
	if req == 0:
		return True
	return False

def answer():
	(l, h) = (0, 10 ** 9)
	ans = -1
	while l <= h:
		mid = (l + h) // 2
		if check(mid):
			ans = mid + 1
			h = mid - 1
		else:
			l = mid + 1
	return ans
for T in range(int(input())):
	(x, s) = map(int, input().split())
	print(answer())