------Read problems statements in Hindi,
Mandarin chinese
, Russian and Vietnamese as well. ------ 

Sheokand is good at mathematics. One day, to test his math skills, Kaali gave him an integer $N$. To impress Kaali, Sheokand has to convert $N$ into an integer $M$ that can be represented in the form $2^{x} + 2^{y}$ (where $x$ and $y$ are non-negative integers such that $x \neq y$). In order to do that, he can perform two types of operations:
add $1$ to $N$
subtract $1$ from $N$

However, Sheokand is preparing for his exams. Can you help him find the minimum number of operations required to convert $N$ into a valid integer $M$?

------  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 testcase contains a single integer $N$.

------  Output ------
For each test case, print a single line containing one integer — the minimum required number of operations.

------  Constraints  ------
$1 ≤ T ≤ 100,000$
$1 ≤ N ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ T ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
3
10
22
4
----- Sample Output 1 ------ 
0
2
1
----- explanation 1 ------ 
Example case 1: $N=10$ is already in the form $2^{x} + 2^{y}$, with $x=3$ and $y=1$.

Example case 2: $N=22$ can be converted into $M=20=2^{2}+2^{4}$ or $M=24=2^{3}+2^{4}$ in two operations.

Example case 3: $N=4$ can be converted into $M=3=2^{0}+2^{1}$ or $M=5=2^{0}+2^{2}$ in one operation.

Source: codechef | Difficulty: MEDIUM
Tags: Number theory

Sorting

Mathematics

Complete search


Solutions:
t = int(input())
arr = []
for i in range(1, 33):
	for j in range(i):
		arr.append((1 << i) + (1 << j))
arr.sort()

def ans(n):
	(low, high) = (0, len(arr))
	(res, diff) = (float('inf'), float('inf'))
	while low <= high:
		mid = (low + high) // 2
		currdiff = abs(n - arr[mid])
		if currdiff < diff:
			diff = currdiff
			res = mid
		if arr[mid] == n:
			return n
		if arr[mid] > n:
			high = mid - 1
		else:
			low = mid + 1
	return arr[res]
for _ in range(t):
	n = int(input())
	print(abs(n - ans(n)))


import bisect
s = set()
for i in range(31):
	for j in range(31):
		if i != j:
			s.add(2 ** i + 2 ** j)
s = list(s)
s.sort()
for _ in range(int(input())):
	n = int(input())
	x = bisect.bisect_left(s, n)
	if s[x] == n:
		print(0)
	elif x != 0:
		print(min(s[x] - n, n - s[x - 1]))
	else:
		print(3 - n)


t = int(input())
for _ in range(t):
	n = int(input())
	s = bin(n)[2:]
	c = s.count('1')
	if n == 1:
		print(2)
	else:
		k = 1
		while k <= n:
			k = k << 1
		k = k >> 1
		if k == n:
			print('1')
		else:
			n = n - k
			j = 1
			while j <= n:
				j = j << 1
			j = j >> 1
			if j * 2 != k:
				print(min(abs(j * 2 - n), abs(j - n)))
			else:
				print(min(abs(j - n), abs(j * 2 + 1 - n)))


for _ in range(int(input())):
	n = int(input())
	s = bin(n)[2:]
	coun = s.count('1')
	if n == 1:
		print(2)
	else:
		cnt = 1
		while cnt <= n:
			cnt = cnt << 1
		cnt = cnt >> 1
		if cnt == n:
			print('1')
		else:
			n = n - cnt
			cnt2 = 1
			while cnt2 <= n:
				cnt2 = cnt2 << 1
			cnt2 = cnt2 >> 1
			if cnt2 * 2 != cnt:
				print(min(abs(cnt2 * 2 - n), abs(cnt2 - n)))
			else:
				print(min(abs(cnt2 - n), abs(cnt2 * 2 + 1 - n)))


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	log = math.log(num, 2)
	if num == 1:
		print(2)
	elif int(log) == log:
		print(1)
	else:
		remaining = num - 2 ** int(log)
		remaining_log = math.floor(math.log(remaining, 2))
		substract = remaining - 2 ** remaining_log
		remaining_log += 1
		add = 2 ** remaining_log - remaining
		ans = min(add, substract)
		if math.log(remaining - ans, 2) != int(math.log(remaining - ans, 2)) and remaining + ans == num - remaining:
			ans += 1
		print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	h = int(math.log(n, 2))
	if n == 1:
		print(2)
	elif n & 1 << h - 1 != 0:
		a = (1 << h) + (1 << h - 1)
		b = (1 << h + 1) + 1
		print(min(n - a, b - n))
	else:
		c = None
		for i in range(h - 1, -1, -1):
			if n & 1 << i != 0:
				c = i
				break
		if c == None:
			print(1)
		elif c == 0:
			print(0)
		else:
			a = (1 << h) + (1 << c + 1)
			b = (1 << h) + (1 << c)
			print(min(a - n, n - b))


import math
L = []
for i in range(31):
	L.append(2 ** i)
A = []
for i in range(31):
	for j in range(i):
		A.append(L[i] + L[j])
A.sort()

def binary_search(A, l, r, x):
	if abs(r - l) <= 1 and l > r:
		if A[l] <= x or r == -1:
			return l
		else:
			return r
	if r >= l:
		mid = l + (r - l) // 2
		if x == A[mid]:
			return mid
		elif x < A[mid]:
			return binary_search(A, l, mid - 1, x)
		else:
			return binary_search(A, mid + 1, r, x)
for i in range(int(input())):
	N = int(input())
	x = binary_search(A, 0, len(A), N)
	if A[x] <= N:
		print(min(abs(A[x + 1] - N), abs(A[x] - N)))
	else:
		print(min(abs(A[x - 1] - N), abs(A[x] - N)))


from math import log2, ceil, floor, inf

def soln(n):
	if n == 1:
		return 2
	res = inf
	prev = floor(log2(n))
	prev_num = 1 << prev
	diff = n - prev_num
	if diff == 0:
		return 1
	nex_diff = (1 << ceil(log2(diff))) - diff
	prev_diff = diff - (1 << floor(log2(diff)))
	if nex_diff < prev_diff:
		res = nex_diff
		if diff + nex_diff == prev_num:
			res += 1
	else:
		res = prev_diff
		if diff - prev_diff == prev_num:
			res += 1
	return res
for _ in range(int(input())):
	n = int(input())
	print(soln(n))


t = int(input())
for _ in range(t):
	n = int(input())
	n_bin = bin(n)[2:]
	count = 0
	i = 0
	while i < len(n_bin):
		if n_bin[i] == '1':
			count += 1
		if count == 2:
			break
		i += 1
	if count == 1:
		if n == 1:
			print(2)
		else:
			print(1)
	elif count == 2 and i == len(n_bin) - 1:
		print(0)
	elif i == 1:
		ans_1 = pow(2, len(n_bin)) + 1
		ans_2 = int('0b' + n_bin[i + 1:], 2)
		print(min(ans_1 - n, ans_2))
	else:
		ans_1 = pow(2, len(n_bin[i:])) - int('0b' + n_bin[i:], 2)
		ans_2 = int('0b' + n_bin[i + 1:], 2)
		print(min(ans_1, ans_2))


n = int(input())
queries = [int(input()) for i in range(n)]

def binary_search(A, value):
	if len(A) == 0:
		return 0
	mid = len(A) // 2
	if A[mid] == value:
		return mid
	elif value < A[mid]:
		return binary_search(A[:mid], value)
	else:
		return mid + 1 + binary_search(A[mid + 1:], value)
A = []
for i in range(0, 40):
	for j in range(i + 1, 40):
		A.append(2 ** i + 2 ** j)
A = sorted(A)
for query in queries:
	value = query
	index = binary_search(A, value)
	print(min([abs(A[i] - value) for i in range(max(0, index - 5), index + 5)]))


from math import log
t = int(input())
for i in range(t):
	a = int(input())
	if log(a, 2) // 1 == log(a, 2):
		if a == 1:
			print(2)
		else:
			print(1)
	else:
		lower = abs(a - 2 ** (log(a, 2) // 1))
		if log(a, 2) // 1 == log(lower, 2) // 1:
			lowerlower = 10000000000
		else:
			lowerlower = abs(lower - 2 ** (log(lower, 2) // 1))
		if log(lower, 2) // 1 + 1 == log(a, 2) // 1:
			lowerupper = 10000000000
		else:
			lowerupper = abs(lower - 2 ** (log(lower, 2) // 1 + 1))
		upper = abs(a - 2 ** (log(a, 2) // 1 + 1)) + 1
		print(int(min((lowerlower, lowerupper, upper))))


def bs(arr, l, h, x):
	if h >= l:
		mid = (h + l) // 2
		if arr[mid] == x:
			return 1
		elif arr[mid] > x:
			return bs(arr, l, mid - 1, x)
		else:
			return bs(arr, mid + 1, h, x)
	else:
		return -1

def bss(arr, l, h, x):
	if h >= l:
		mid = (h + l) // 2
		if arr[mid] > x:
			if arr[mid - 1] < x:
				print(min(x - arr[mid - 1], arr[mid] - x))
			else:
				bss(arr, l, mid - 1, x)
		elif arr[mid] < x:
			if arr[mid + 1] > x:
				print(min(x - arr[mid], arr[mid + 1] - x))
			else:
				bss(arr, mid + 1, h, x)
a = []
for i in range(31):
	for j in range(31):
		if i != j:
			a.append(2 ** j + 2 ** i)
a = list(set(a))
a.sort()
for _ in range(int(input())):
	n = int(input())
	m = bs(a, 0, len(a) - 1, n)
	if m == 1:
		print('0')
	elif m == -1 and n >= 3:
		p = bss(a, 0, len(a) - 1, n)
	else:
		print(3 - n)


from bisect import bisect, insort

def bisect_right(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x < a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return a[i - 1]
	raise ValueError

def find_gt(a, x):
	i = bisect_right(a, x)
	if i != len(a):
		return a[i]
	raise ValueError
possible_m = []
for i in range(31):
	for j in range(31):
		if i != j:
			possible_m.append(2 ** i + 2 ** j)
possible_m = sorted(possible_m)
t = int(input())
for i in range(t):
	n = int(input())
	if n < 3:
		print(3 - n)
	else:
		print(min(n - find_le(possible_m, n), find_gt(possible_m, n) - n))


import sys
import os
import math
import collections

def search(N, ans):
	(l, r) = (0, len(ans))
	while l <= r:
		mid = (l + r) // 2
		if ans[mid] == N:
			return mid
		elif ans[mid] < N:
			l = mid + 1
		else:
			r = mid - 1
		if l == len(ans):
			return l
	return l
T = int(input())
ans = []
for i in range(31):
	for j in range(i + 1, 31):
		x = (1 << i) + (1 << j)
		ans.append(x)
ans.sort()
for _ in range(T):
	N = int(input())
	A = search(N, ans)
	print(min(abs(ans[A] - N), abs(ans[A - 1] - N)))


T = int(input())
lst = []
for i in range(31):
	for j in range(i):
		lst.append(2 ** i + 2 ** j)
lst.sort()

def bound_search(lst, x, compare):
	lo = 0
	up = len(lst)
	while lo < up:
		mid = (lo + up) // 2
		if compare(x, lst[mid]):
			up = mid
		else:
			lo = mid + 1
	return lo
upper = lambda x, elem: x < elem
while T > 0:
	N = int(input())
	nxt = bound_search(lst, N, upper)
	prev = bound_search(lst, N, upper) - 1
	ans = min(abs(N - lst[nxt]), abs(N - lst[prev]))
	print(ans)
	T -= 1


lst = []
for i in range(32):
	for j in range(32):
		if i != j:
			lst.append(2 ** i + 2 ** j)
l = sorted(list(set(lst)))

def bin_search(x):
	low = 0
	high = len(l) - 1
	while low < high:
		mid = low + (high - low) // 2
		if x < l[mid]:
			high = mid - 1
		else:
			low = mid + 1
	return min(abs(x - l[low]), abs(x - l[low - 1]), abs(x - l[low + 1]))
d = {}
for _ in range(int(input())):
	n = int(input())
	a = bin_search(n)
	if n not in d:
		print(a)
		d[n] = a
	else:
		print(d[n])


def bin(arr, i, j, val):
	while i <= j:
		mid = (i + j) // 2
		if arr[mid] == val or (arr[mid] < val and val < arr[mid + 1]):
			return mid
		elif arr[mid] < val:
			i = mid + 1
		elif arr[mid] > val:
			j = mid - 1
li = []
for i in range(31):
	for j in range(31):
		if i != j:
			li.append(2 ** i + 2 ** j)
li.sort()
for l in range(int(input())):
	N = int(input())
	if N == 1:
		print(2)
	elif N == 2:
		print(1)
	else:
		i = bin(li, 0, len(li) - 1, N)
		print(min(N - li[i], li[i + 1] - N))


lst = []
for i in range(32):
	for j in range(32):
		if i != j:
			lst.append(2 ** i + 2 ** j)
lst.sort()

def bin_search(x, low, high):
	if low > high:
		return min(abs(x - lst[low]), abs(x - lst[low - 1]), abs(x - lst[low + 1]))
	else:
		mid = low + (high - low) // 2
		if x == lst[mid]:
			return 0
		elif x < lst[mid]:
			return bin_search(x, low, mid - 1)
		else:
			return bin_search(x, mid + 1, high)
d = {}
T = int(input())
for k in range(T):
	N = int(input())
	a = bin_search(N, 0, len(lst) - 1)
	if N not in d:
		print(a)
		d[N] = a
	else:
		print(d[N])


from bisect import bisect_left

def twsqr():
	sqrs = []
	for i in range(33):
		for j in range(33):
			sqrs.append(2 ** i + 2 ** j)
	sqrs = list(set(sqrs))
	sqrs.sort()
	for k in range(1, 33):
		n = int(2 ** k)
		sqrs.remove(n)
	return sqrs
sqrs = twsqr()
for _ in range(int(input())):
	n = int(input())
	ans = 0
	if n == 1:
		ans = 2
	elif n == 2:
		ans = 1
	elif n in sqrs:
		ans = 0
	else:
		leftind = bisect_left(sqrs, n)
		f1 = int(n - sqrs[leftind - 1])
		f2 = int(sqrs[leftind] - n)
		if f1 > f2:
			ans = f2
		else:
			ans = f1
	print(ans)


nums = []
for x in range(33):
	for y in range(33):
		if x == y:
			continue
		nums.append(2 ** x + 2 ** y)
nums.sort()

def binary_search(lo, hi, condition, target):
	while lo <= hi:
		mid = (lo + hi) // 2
		result = condition(mid)
		if result == 'found':
			if nums[mid] == target:
				return 0
			elif nums[mid] < target < nums[mid + 1]:
				return min(abs(nums[mid + 1] - target), abs(nums[mid] - target))
			else:
				return min(abs(nums[mid - 1] - target), abs(nums[mid] - target))
		elif result == 'left':
			hi = mid - 1
		else:
			lo = mid + 1
	return -1

def find_num(nums, target):

	def condition(mid):
		if nums[mid] == target or nums[mid] < target < nums[mid + 1] or nums[mid - 1] < target < nums[mid]:
			return 'found'
		elif nums[mid] < target:
			return 'right'
		else:
			return 'left'
	return binary_search(0, len(nums) - 1, condition, target)
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	elif n == 2:
		print(1)
	else:
		print(find_num(nums, n))


from bisect import bisect_right, bisect_left
lst = set()
for i in range(31):
	for j in range(31):
		if i != j:
			lst.add(2 ** i + 2 ** j)
lst = sorted(list(lst))
t = int(input())
for _ in range(t):
	n = int(input())
	t1 = bisect_left(lst, n)
	t2 = bisect_right(lst, n)
	print(min(abs(lst[t1] - n), abs(lst[t2 - 1] - n)))


import math
for _ in range(int(input())):
	N = int(input())
	l = 0
	h = 1
	while math.floor(N / 2 ** h) > 0:
		h += 1
	ans = 10 ** 9 + 1
	while l < h:
		cnt = 2 ** l + 2 ** h
		ans = min(abs(cnt - N), ans)
		if cnt == N:
			break
		elif cnt < N:
			l += 1
		else:
			h -= 1
	print(ans)


l = []
for i in range(32):
	for j in range(32):
		if i != j:
			l.append(2 ** i + 2 ** j)
la = sorted(list(set(l)))

def binary(x):
	lo = 0
	high = len(la) - 1
	while lo < high:
		mid = (lo + high) // 2
		if x < la[mid]:
			high = mid - 1
		else:
			lo = mid + 1
	return min(abs(x - la[lo]), abs(x - la[lo + 1]), abs(x - la[lo - 1]))
d = {}
for _ in range(int(input())):
	n = int(input())
	p = binary(n)
	if n not in d:
		print(p)
		d[n] = p
	else:
		print(d[n])


from sys import stdin, stdout, maxsize
from bisect import bisect_left, bisect_right, bisect
l = []
for i in range(0, 31):
	for j in range(0, 31):
		if i != j:
			l.append(2 ** i + 2 ** j)
la = sorted(list(set(l)))

def binary(x):
	lo = 0
	high = len(la) - 1
	while lo < high:
		mid = (lo + high) // 2
		if la[mid] < n:
			lo = mid + 1
		else:
			high = mid - 1
	return min(abs(x - la[lo]), abs(x - la[lo + 1]), abs(x - la[lo - 1]))
q = int(stdin.readline())
d = {}
for _ in range(q):
	n = int(stdin.readline())
	if n not in d:
		z = binary(n)
		print(z)
		d[n] = z
	else:
		print(d[n])


import math
test = int(input())
while test != 0:
	data = int(input())
	if data == 1:
		print(2)
		test -= 1
		continue
	low = math.floor(math.log(data, 2))
	high = math.ceil(math.log(data, 2))
	if high == low:
		print(1)
		test -= 1
		continue
	pvt = math.log(abs(data - pow(2, low)), 2)
	low1 = math.floor(pvt)
	high1 = math.ceil(pvt)
	a = abs(data - (pow(2, low1) + pow(2, low)))
	b = abs(data - (pow(2, low) + pow(2, high1)))
	to_sub = 0
	flag = 0
	if high1 != low:
		if a <= b:
			to_sub = a
		else:
			to_sub = b
	else:
		to_sub = a
	if to_sub <= abs(data - (pow(2, high) + 1)):
		print(to_sub)
	else:
		print(abs(data - (pow(2, high) + 1)))
	test -= 1


l = []
for i in range(31):
	for j in range(i + 1, 31):
		l.append(2 ** i + 2 ** j)
l.sort()

def getClosest(val1, val2, target):
	if target - val1 >= val2 - target:
		return val2
	else:
		return val1

def findClosest(l1, target):
	i = 0
	j = l1
	mid = 0
	while i < j:
		mid = (i + j) // 2
		if l[mid] == target:
			return l[mid]
		if target < l[mid]:
			if mid > 0 and target > l[mid - 1]:
				return getClosest(l[mid - 1], l[mid], target)
			j = mid
		else:
			if mid < n - 1 and target < l[mid + 1]:
				return getClosest(l[mid], l[mid + 1], target)
			i = mid + 1
	return arr[mid]
for t in range(int(input())):
	n = int(input())
	l1 = len(l)
	ans = 0
	if n <= 3:
		print(3 - n)
	else:
		print(abs(findClosest(l1, n) - n))


l = []
for i in range(31):
	for j in range(i + 1, 31):
		l.append(2 ** i + 2 ** j)
l1 = len(l)
l.sort()
for t in range(int(input())):
	n = int(input())
	ans = 0
	if n <= 3:
		print(3 - n)
	else:
		for i in range(l1):
			if l[i] >= n:
				ans = min(l[i] - n, n - l[i - 1])
				break
		print(ans)


import math
t = int(input())
for x in range(t):
	p = int(input())
	a = int(math.log(p, 2))
	b = int(pow(2, a))
	l = abs(p - b)
	if p == 1:
		print(2)
		continue
	if p == 4:
		print(1)
		continue
	if p == 2:
		print(1)
		continue
	if l == 0:
		print(1)
		continue
	else:
		c = math.ceil(math.log(l) / math.log(2))
		d = math.floor(math.log(l) / math.log(2))
		e = abs(p - (b + pow(2, c)))
		f = abs(p - (b + pow(2, d)))
		if a == c and abs(p - (1 + pow(2, c + 1))) < f:
			print(min(e, f) + 1)
		else:
			print(min(e, f))


def bin(start, end):
	while start < end:
		mid = (start + end) // 2
		if la[mid] < n:
			start = mid + 1
		else:
			end = mid - 1
	return min(abs(n - la[start]), abs(n - la[start + 1]), abs(n - la[start - 1]))
la = []
for i in range(35):
	for j in range(35):
		if i != j:
			la.append(2 ** i + 2 ** j)
la = sorted(list(set(la)))
hash = {}
t = int(input())
for _ in range(t):
	n = int(input())
	mini = 10 ** 18
	if n not in hash:
		z = bin(0, len(la) - 1)
		print(z)
		hash[n] = z
	else:
		print(hash[n])


a = [1, 2]
for i in range(29):
	a.append(a[-1] * 2)
c = []
for i in range(len(a) - 1):
	k = a[i]
	for j in range(i + 1, len(a)):
		c.append(k + a[j])
c.sort()
for i in range(int(input())):
	l = int(input())
	if l <= 3:
		print(3 - l)
	else:
		for j in range(465):
			if c[j] >= l:
				print(min(c[j] - l, l - c[j - 1]))
				break


import bisect
a = []
for i in range(0, 31):
	for j in range(i + 1, 31):
		x = (1 << i) + (1 << j)
		a.append(x)
a = sorted(a)
for i in range(int(input())):
	N = int(input())
	k = bisect.bisect(a, N, 0, len(a))
	if k <= 464 and k >= 1:
		print(min(a[k] - N, N - a[k - 1]))
	elif k < 1:
		print(a[k] - N)


import math
for _ in range(int(input())):
	n = int(input())
	c1 = math.ceil(math.log(n, 2))
	c2 = math.floor(math.log(n, 2))
	if n == 1:
		print(2)
	elif c1 == c2:
		print(1)
	else:
		k = n - pow(2, c2)
		c3 = math.ceil(math.log(k, 2))
		c4 = math.floor(math.log(k, 2))
		if c3 == c4:
			print(0)
		else:
			if c2 != c3:
				ans = pow(2, c3) + pow(2, c2) - n
			else:
				ans = pow(2, c3) + pow(2, c2) + 1 - n
			res = n - pow(2, c4) - pow(2, c2)
			if ans >= res:
				print(res)
			else:
				print(ans)


import bisect

def find_le(a, x):
	i = bisect.bisect_right(a, x)
	if i:
		return a[i - 1]

def find_gr(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a):
		return a[i]
l = list()
for i in range(0, 31):
	for j in range(0, 31):
		if i != j:
			l.append(2 ** i + 2 ** j)
l.sort()
t = int(input())
for i in range(0, t):
	N = int(input())
	ans = 0
	if N < 3:
		ans = 3 - N
	else:
		ans = min(N - find_le(l, N), find_gr(l, N) - N)
	print(ans)


from bisect import bisect
vals = []
for i in range(0, 32):
	for j in range(i + 1, 32):
		x = (1 << i) + (1 << j)
		vals.append(x)
vals.sort()
t = int(input())
for i in range(t):
	n = int(input())
	index = bisect(vals, n)
	if index <= 528 and index >= 1:
		min1 = vals[index] - n
		min2 = n - vals[index - 1]
		print(min(min1, min2))
	elif index < 1:
		print(vals[index] - n)
	else:
		print(n - vals[528])


from bisect import bisect
vals = []
for i in range(0, 31):
	for j in range(i + 1, 31):
		x = (1 << i) + (1 << j)
		vals.append(x)
vals.sort()
t = int(input())
for i in range(t):
	n = int(input())
	j = 0
	while True:
		if vals[j] >= n:
			break
		j = j + 1
	print(min(abs(vals[j] - n), abs(vals[j - 1] - n)))


from bisect import bisect
vals = []
for i in range(0, 31):
	for j in range(i + 1, 31):
		x = (1 << i) + (1 << j)
		vals.append(x)
vals.sort()
t = int(input())
l = len(vals)
for i in range(t):
	n = int(input())
	index = bisect(vals, n)
	if index <= l - 1 and index >= 1:
		min1 = vals[index] - n
		min2 = n - vals[index - 1]
		print(min(min1, min2))
	elif index < 1:
		print(vals[index] - n)
	else:
		print(n - vals[l - 1])


from sys import stdin
Num = [3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516, 520, 528, 544, 576, 640, 768, 1025, 1026, 1028, 1032, 1040, 1056, 1088, 1152, 1280, 1536, 2049, 2050, 2052, 2056, 2064, 2080, 2112, 2176, 2304, 2560, 3072, 4097, 4098, 4100, 4104, 4112, 4128, 4160, 4224, 4352, 4608, 5120, 6144, 8193, 8194, 8196, 8200, 8208, 8224, 8256, 8320, 8448, 8704, 9216, 10240, 12288, 16385, 16386, 16388, 16392, 16400, 16416, 16448, 16512, 16640, 16896, 17408, 18432, 20480, 24576, 32769, 32770, 32772, 32776, 32784, 32800, 32832, 32896, 33024, 33280, 33792, 34816, 36864, 40960, 49152, 65537, 65538, 65540, 65544, 65552, 65568, 65600, 65664, 65792, 66048, 66560, 67584, 69632, 73728, 81920, 98304, 131073, 131074, 131076, 131080, 131088, 131104, 131136, 131200, 131328, 131584, 132096, 133120, 135168, 139264, 147456, 163840, 196608, 262145, 262146, 262148, 262152, 262160, 262176, 262208, 262272, 262400, 262656, 263168, 264192, 266240, 270336, 278528, 294912, 327680, 393216, 524289, 524290, 524292, 524296, 524304, 524320, 524352, 524416, 524544, 524800, 525312, 526336, 528384, 532480, 540672, 557056, 589824, 655360, 786432, 1048577, 1048578, 1048580, 1048584, 1048592, 1048608, 1048640, 1048704, 1048832, 1049088, 1049600, 1050624, 1052672, 1056768, 1064960, 1081344, 1114112, 1179648, 1310720, 1572864, 2097153, 2097154, 2097156, 2097160, 2097168, 2097184, 2097216, 2097280, 2097408, 2097664, 2098176, 2099200, 2101248, 2105344, 2113536, 2129920, 2162688, 2228224, 2359296, 2621440, 3145728, 4194305, 4194306, 4194308, 4194312, 4194320, 4194336, 4194368, 4194432, 4194560, 4194816, 4195328, 4196352, 4198400, 4202496, 4210688, 4227072, 4259840, 4325376, 4456448, 4718592, 5242880, 6291456, 8388609, 8388610, 8388612, 8388616, 8388624, 8388640, 8388672, 8388736, 8388864, 8389120, 8389632, 8390656, 8392704, 8396800, 8404992, 8421376, 8454144, 8519680, 8650752, 8912896, 9437184, 10485760, 12582912, 16777217, 16777218, 16777220, 16777224, 16777232, 16777248, 16777280, 16777344, 16777472, 16777728, 16778240, 16779264, 16781312, 16785408, 16793600, 16809984, 16842752, 16908288, 17039360, 17301504, 17825792, 18874368, 20971520, 25165824, 33554433, 33554434, 33554436, 33554440, 33554448, 33554464, 33554496, 33554560, 33554688, 33554944, 33555456, 33556480, 33558528, 33562624, 33570816, 33587200, 33619968, 33685504, 33816576, 34078720, 34603008, 35651584, 37748736, 41943040, 50331648, 67108865, 67108866, 67108868, 67108872, 67108880, 67108896, 67108928, 67108992, 67109120, 67109376, 67109888, 67110912, 67112960, 67117056, 67125248, 67141632, 67174400, 67239936, 67371008, 67633152, 68157440, 69206016, 71303168, 75497472, 83886080, 100663296, 134217729, 134217730, 134217732, 134217736, 134217744, 134217760, 134217792, 134217856, 134217984, 134218240, 134218752, 134219776, 134221824, 134225920, 134234112, 134250496, 134283264, 134348800, 134479872, 134742016, 135266304, 136314880, 138412032, 142606336, 150994944, 167772160, 201326592, 268435457, 268435458, 268435460, 268435464, 268435472, 268435488, 268435520, 268435584, 268435712, 268435968, 268436480, 268437504, 268439552, 268443648, 268451840, 268468224, 268500992, 268566528, 268697600, 268959744, 269484032, 270532608, 272629760, 276824064, 285212672, 301989888, 335544320, 402653184, 536870913, 536870914, 536870916, 536870920, 536870928, 536870944, 536870976, 536871040, 536871168, 536871424, 536871936, 536872960, 536875008, 536879104, 536887296, 536903680, 536936448, 537001984, 537133056, 537395200, 537919488, 538968064, 541065216, 545259520, 553648128, 570425344, 603979776, 671088640, 805306368, 1073741825, 1073741826, 1073741828, 1073741832, 1073741840, 1073741856, 1073741888, 1073741952, 1073742080, 1073742336, 1073742848, 1073743872, 1073745920, 1073750016, 1073758208, 1073774592, 1073807360, 1073872896, 1074003968, 1074266112, 1074790400, 1075838976, 1077936128, 1082130432, 1090519040, 1107296256, 1140850688, 1207959552, 1342177280, 1610612736]
t = len(Num)
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	(l, h) = (0, t - 1)
	while l < h:
		m = (l + h) // 2
		if n == Num[m]:
			break
		elif n > Num[m]:
			l = m + 1
		else:
			h = m
	print(min(abs(n - Num[m - 1]), abs(n - Num[m]), abs(Num[m + 1] - n)))


var = []
for i in range(0, 32):
	for j in range(i + 1, 32):
		var.append(2 ** i + 2 ** j)
var.sort()
for i in range(int(input())):
	n = int(input())
	j = 0
	while True:
		if var[j] >= n:
			break
		j += 1
	print(min(abs(var[j] - n), abs(var[j - 1] - n)))


vals = []
for i in range(0, 32):
	for j in range(i + 1, 32):
		num = (1 << i) + (1 << j)
		vals.append(num)
vals.sort()
for t in range(int(input())):
	num = int(input())
	i = 0
	while True:
		if vals[i] >= num:
			break
		i += 1
	print(min(abs(vals[i] - num), abs(vals[i - 1] - num)))


def close(n):
	for i in range(31):
		if n == arr[i]:
			return (arr[i], arr[i])
		if n > arr[i] and n < arr[i + 1]:
			return (arr[i], arr[i + 1])

def calx(n, min):
	(a, b) = close(n)
	if a == b and b == min:
		return b / 2
	if a == b:
		return a
	if b == min:
		return a
	if a == min:
		return a / 2
	if b - n >= n - a:
		return a if a != min else a / 2
	if b - n < n - a:
		return b if b != min else b / 2
arr = []
for i in range(31):
	arr.append(2 ** i)
t = int(input())
for i in range(t):
	num = int(input())
	(min, max) = close(num)
	if num == 1:
		print('2')
	elif min == max:
		print('1')
	else:
		maxd = max + 1 - num
		mind = abs(min + calx(num - min, min) - num)
		diff = maxd if maxd < mind else mind
		print(diff)


import math
T = int(input())
for i in range(0, T):
	N = int(input())
	if N == 1:
		print(2)
	elif N - 2 ** int(math.log2(N)) == 0:
		print(1)
	else:
		x = int(math.log2(N))
		diff1 = N - 2 ** x
		y = int(math.log2(diff1))
		diff2 = diff1 - 2 ** y
		if diff2 <= 2 ** y - diff2:
			print(diff2)
		elif diff2 > 2 ** y - diff2 and x - y == 1:
			print(2 ** y - diff2 + 1)
		elif diff2 > 2 ** y - diff2:
			print(2 ** y - diff2)


def cal(num):
	x = 0
	while pow(2, x) < num:
		x = x + 1
	return x - 1
n = int(input())
for i in range(0, n):
	num = int(input())
	if num == 1:
		print(2)
	elif num == 2:
		print(1)
	else:
		x = cal(num)
		num1 = num - pow(2, x)
		y = cal(num1)
		if num > pow(2, x - 1) + pow(2, x):
			print(min(num1 - pow(2, y), pow(2, x + 1) + 1 - num))
		else:
			print(min(num1 - pow(2, y), pow(2, y + 1) - num1))


t = int(input())
x = []
for i in range(0, 31):
	for j in range(i + 1, 31):
		k = (1 << i) + (1 << j)
		x.append(k)
x.sort()

def search(n):
	i = int(0)
	while i < len(x):
		if x[i] > n:
			break
		i = i + 1
	return i
while t > 0:
	n = int(input())
	result = search(n)
	m = int(0)
	if result == 0:
		m = x[0] - n
	elif result == len(x):
		m = n - x[result]
	else:
		a = x[result] - n
		b = n - x[result - 1]
		if a < b:
			m = a
		else:
			m = b
	print(m)
	t -= 1


import math
T = int(input())
for i in range(T):
	a = int(input())
	b = math.log(a, 2)
	val = int(b)
	if a == 1:
		print('2')
	elif val == b:
		print('1')
	else:
		l = a - 2 ** val
		c = int(math.log(l, 2))
		g = l - 2 ** c
		g3 = abs(l - 2 ** (c + 1))
		g2 = 2 ** (val + 1) + 1
		val_net = g2 - a
		if c + 1 == val:
			print(min(val_net, g))
		else:
			print(min(val_net, g, g3))


import math
T = int(input())
for i in range(T):
	a = int(input())
	b = math.log(a) / math.log(2)
	val = int(b)
	if a == 1:
		print('2')
	elif val == b:
		print('1')
	else:
		rem = a - 2 ** val
		c = int(math.log(rem) / math.log(2))
		val_1 = rem - 2 ** c
		val_3 = abs(rem - 2 ** (c + 1))
		val_2 = 2 ** (val + 1) + 1
		val_net = val_2 - a
		if c + 1 == val:
			print(min(val_net, val_1))
		else:
			print(min(val_net, val_1, val_3))


from functools import reduce
t = int(input())
for _ in range(t):
	test_case = int(input())
	if test_case != 1:
		bin_test = bin(test_case)[2:]
		n = reduce(lambda x, y: int(x) + int(y), bin_test)
		index_first = len(bin_test) - 1
		index_second = -1
		for i in range(1, len(bin_test)):
			if bin_test[i] == '1':
				index_second = len(bin_test) - i - 1
				break
		output = 1 if n == 1 else 0
		if n > 2:
			mask = (1 << index_second) - 1
			output = test_case & mask
			shift = 1 << index_second + 1
			mask2 = shift - 1
			output2 = shift - (test_case & mask2)
			if index_first == index_second + 1:
				output2 += 1
			if output > output2:
				output = output2
	else:
		output = 2
	print(output)