Given a long integer $\boldsymbol{x}$, count the number of values of $\class{ML__boldsymbol}{\boldsymbol{a}}$ satisfying the following conditions:  

$a\oplus x>x$
$0<a<x$

where $\class{ML__boldsymbol}{\boldsymbol{a}}$ and $\boldsymbol{x}$ are long integers and $\oplus$ is the bitwise XOR operator.  

You are given $\textit{q}$ queries, and each query is in the form of a long integer denoting $\boldsymbol{x}$. For each query, print the total number of values of $\class{ML__boldsymbol}{\boldsymbol{a}}$ satisfying the conditions above on a new line.

For example, you are given the value $x=5$.  Condition $2$ requires that $\class{ML__boldsymbol}{\boldsymbol{a}}<x$.  The following tests are run:  

$1\oplus5=4$ 

$2\oplus5=7$ 

$3\oplus5=6$ 

$4\oplus5=1$   

We find that there are $2$ values meeting the first condition: $2$ and $3$.  

Function Description  

Complete the theGreatXor function in the editor below.  It should return an integer that represents the number of values satisfying the constraints.  

theGreatXor has the following parameter(s):

x: an integer  

Input Format

The first line contains an integer $\textit{q}$, the number of queries. 

Each of the next $\textit{q}$ lines contains a long integer describing the value of $\boldsymbol{x}$ for a query.  

Constraints

$1\leq q\leq10^5$
$1\leq x\leq10^{10}$

Subtasks

For $50\%$ of the maximum score:

$1\leq q\leq10^3$
$1\leq x\leq10^4$

Output Format

For each query, print the number of values of $\class{ML__boldsymbol}{\boldsymbol{a}}$ satisfying the given conditions on a new line.

Sample Input 0
2
2
10

Sample Output 0
1
5

Explanation 0

We perform the following $q=2$ queries:

For $x=2$ the only value of $\class{ML__boldsymbol}{\boldsymbol{a}}$ satisfying $0<a<x$ is $1$. This also satisfies our other condition, as $1\oplus2=3$ and $3>x$. Because we have one valid $\class{ML__boldsymbol}{\boldsymbol{a}}$ and there are no more values to check, we print $1$ on a new line.

For $x=10$, the following values of $\class{ML__boldsymbol}{\boldsymbol{a}}$ satisfy our conditions:

$1\oplus10=11$ 

$4\oplus10=14$ 

$5\oplus10=15$ 

$6\oplus10=12$ 

$7\oplus10=13$

There are five valid values of $\class{ML__boldsymbol}{\boldsymbol{a}}$.

Sample Input 1
2
5
100

Sample Output 1
2
27

Explanation 1

In the first case: 

$2\oplus5=7$ 

$3\oplus5=6$ 

In the second case, the first 10 values are: 

$1\oplus100=101$ 

$2\oplus100=102$ 

$3\oplus100=103$ 

$8\oplus100=108$ 

$9\oplus100=109$ 

$10\oplus100=110$ 

$11\oplus100=111$ 

$\textbf{12}\oplus100=104$ 

$13\oplus100=105$ 

$14\oplus100=106$ 

$15\oplus100=107$

Source: hackerrank | Difficulty: MEDIUM
Tags: Bit manipulation


Solutions:
import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	size = 1
	result = 0
	while x > 0:
		if x & 1 == 0:
			result += size
		size *= 2
		x = x >> 1
	print(result)


import sys
q = int(input().strip())
for a0 in range(q):
	x = str(bin(int(input().strip())))[2:]
	count = 0
	for i in range(1, len(x) + 1):
		if x[-i] == '0':
			count += 2 ** (i - 1)
	print(count)


import sys
q = int(input().strip())
for a0 in range(q):
	x = bin(int(input().strip()))[2:]
	n = len(x)
	total = 0
	for i in range(1, n):
		if x[i] == '0':
			total += 2 ** (n - i - 1)
	print(total)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	b = '{0:b}'.format(x)
	ans = 0
	for i in range(len(b)):
		if b[i] == '0':
			ans += 2 ** (len(b) - i - 1)
	print(ans)


import sys

def c(x):
	rv = 0
	t = 1
	while x > 0:
		if x & 1 == 0:
			rv += t
		x >>= 1
		t <<= 1
	return rv
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(c(x))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	count = 0
	term = 1
	while x:
		if x & 1 == 0:
			count += term
		term *= 2
		x //= 2
	print(count)


for _ in range(int(input())):
	x = int(input())
	print((1 << x.bit_length()) - 1 - x)


for _ in range(int(input())):
	x = int(input())
	print(sum((1 << i for i in range(40) if not x & 1 << i and 1 << i < x)))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	cnt = 0
	for (pos, bit) in enumerate(bin(x)[::-1]):
		if bit == 'b':
			break
		if bit == '0':
			cnt += int(2 ** pos)
	print(cnt)


import sys
data = sys.stdin.read().splitlines()
for x in map(int, data[1:]):
	y = 2 ** (len('{0:b}'.format(x)) - 1) - 1
	print(2 * y - x + 1)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	s = 0
	cnt = 0
	while x > 0:
		if x % 2 == 0:
			s += int(pow(2, cnt))
		cnt += 1
		x = int(x / 2)
	print(s)


import sys

def num_great_xors(n):
	st_n = '{0:b}'.format(n)
	result = 0
	for i in range(len(st_n)):
		if st_n[-1 - i] == '0':
			result += 2 ** i
	return result
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(num_great_xors(x))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	ans = 0
	j = 1
	while x:
		if x % 2 == 0:
			ans += j
		j *= 2
		x //= 2
	print(ans)


import sys
totals = []
q = int(input().strip())
for a0 in range(q):
	total = 0
	x = int(input().strip())
	length = len(bin(x)) - 2
	for (pos, val) in enumerate(bin(x)[2:]):
		if val == '0':
			total += pow(2, length - pos - 1)
	totals.append(total)
for i in totals:
	print(i)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	x = bin(x)
	x = x[2:]
	x = [i for i in x]
	x.reverse()
	x = ''.join(x)
	S = 0
	for i in range(0, len(x)):
		if x[i] == '0':
			S = S + 2 ** i
	print(str(S))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	count = 0
	for i in range(x.bit_length()):
		mask = x >> 1
		mask <<= 1
		last_bit = x ^ mask
		if last_bit == 0:
			count += 2 ** i
		x >>= 1
	print(count)


import sys
from math import ceil, log
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(2 ** ceil(log(x + 1, 2)) - 1 ^ x)


q = int(input())
for _ in range(q):
	x = bin(int(input()))[2:]
	ans = 0
	for i in range(len(x)):
		tmp = len(x) - i - 1
		if x[tmp] == '0':
			ans += 2 ** i
	print(ans)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	nb = bin(x)[2:][::-1]
	total = 0
	for i in range(len(nb)):
		if nb[i] == '0':
			total += 2 ** i
	print(total)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	tot = 0
	bx = [int(i) for i in list(bin(x)[2:])]
	bx.reverse()
	for j in range(len(bx)):
		if bx[j] == 0:
			tot += 2 ** j
	print(tot)


import sys

def nGreaterXOR(x):
	n = 0
	w = 1
	while x:
		if x & 1 == 0:
			n += w
		x >>= 1
		w <<= 1
	return n
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(nGreaterXOR(x))


def bits(n):
	m = 1
	while m <= n:
		yield (n & m)
		m <<= 1
for _ in range(int(input())):
	x = int(input())
	mask = (1 << len(bin(x)) - 2) - 1
	print(sum(bits(x ^ mask)))


import sys

def largestTwo(n):
	return 2 ** (len(bin(n)[2:]) - 1)
q = int(input().strip())
values = []
dictionary = {}
for a0 in range(q):
	x = int(input().strip())
	if x in dictionary:
		print(dictionary[x])
	else:
		twoPower = largestTwo(x)
		modValue = x % twoPower
		val = twoPower - (modValue + 1)
		dictionary[x] = val
		print(val)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	total = 0
	binX = bin(x)[2:]
	l = len(binX)
	for i in range(l):
		if binX[i] == '0':
			total += pow(2, l - i - 1)
	print(total)


q = int(input())
for i in range(q):
	x = int(input())
	x = bin(x)[2:]
	if '0' not in x:
		print(0)
	else:
		n = len(x) - x.find('0')
		total = 2 ** n - 1
		ms = []
		for (i, b) in enumerate(x[::-1]):
			if i == n:
				break
			elif b == '1':
				ms.append(i)
		for j in ms:
			total -= 2 ** j
		print(total)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	cp = 1
	ans = 0
	while cp <= x:
		if x ^ cp > x:
			ans = ans + cp
		cp = cp << 1
	print(ans)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	answer = 0
	for i in range(0, 33):
		if 1 << i >= x:
			break
		if 0 == x & 1 << i:
			answer = answer + (1 << i)
	print(answer)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	a = bin(x)
	a = a[2:]
	a = a[::-1]
	s = 0
	for i in range(len(a)):
		if a[i] == '0':
			s += pow(2, i)
	print(s)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	bin_int = bin(x)[2:]
	acc = 0
	for (index, num) in enumerate(bin_int[::-1]):
		if num == '0':
			acc += 2 ** index
	print(acc)


q = int(input().strip())
for _ in range(q):
	x = int(input().strip())
	i = 1
	a = 0
	while x > 1:
		if x & 1 == 0:
			a += i
		x >>= 1
		i *= 2
	print(a)


def solve(n):
	_bin = '{0:b}'.format(n)
	i = len(_bin) - 1
	ans = 0
	for bit in _bin:
		if bit == '0':
			ans += pow(2, i)
		i -= 1
	print(ans)
for i in range(int(input())):
	solve(int(input()))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	xt = '{0:035b}'.format(x)
	at = '{0:035b}'.format(a0)
	st_inx = xt.index('1')
	res = 0
	for inx in range(st_inx + 1, len(xt)):
		if xt[inx] == '0':
			res += int(2 ** (len(xt) - 1 - inx))
	print(res)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	bits = x.bit_length()
	if 2 ** bits > x:
		bits -= 1
	num = x - 2 ** bits
	print(x - (num * 2 + 1))


import sys
q = int(input().strip())
for a0 in range(q):
	x = bin(int(input().strip())).split('b')[1]
	sz = len(x)
	sum = 0
	for i in range(sz):
		if x[i] == '0':
			sum += 2 ** (sz - i - 1)
	print(sum)


import sys
from math import floor, log2
q = int(input().strip())
r = []
for a0 in range(q):
	c = 0
	x = int(input().strip())
	n = floor(log2(x))
	y = bin(x)[2:]
	for i in range(1, n + 1):
		if y[i] == '0':
			c += pow(2, n + 1 - i) // 2
	r.append(c)
for i in r:
	print(i)


import math
import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	if x & x - 1 == 0:
		print(x - 1)
	else:
		d = math.ceil(math.log(x) / math.log(2))
		print(2 ** d - 1 - x)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(2 ** x.bit_length() - 1 - x)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	b = str(bin(x))[2:]
	c = len(b)
	sum = 0
	for i in range(c):
		if b[i] == '1':
			continue
		elif b[i] == '0':
			sum += 2 ** (c - i - 1)
	print(sum)


T = int(input())
for _ in range(0, T):
	s = bin(int(input()))
	cnt = 0
	n = len(s)
	for x in range(3, n):
		if s[x] == '0':
			cnt += 1 << n - 1 - x
	print(cnt)


import sys
import math
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	t = int(math.log(x, 2)) + 1
	print(2 ** t - x - 1)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	len_x = len(bin(x)) - 2
	c = 0
	for i in range(len_x - 1):
		v = 1 << i
		if x & v != v:
			c += 2 ** i
	val = x - 2 ** (len_x - 1) + 1
	v = 1 << len_x - 1
	if x & v != v:
		c += val
	print(c)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	zeros = pow(2, x.bit_length()) - 1 ^ x
	print(zeros)


import sys
q = int(input())
for i in range(q):
	a = list(map(int, list('{0:b}'.format(int(input())))))
	ans = 0
	n = len(a)
	for i in range(n):
		if not a[i]:
			ans += 1 << n - i - 1
	print(ans)


import sys

def BinaryOf(x):
	l = []
	r = x
	n = x
	while n != 1:
		r = n % 2
		l.append(r)
		n = n // 2
	l.append(n)
	return l
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	count = 0
	l = BinaryOf(x)
	index = []
	for i in range(len(l)):
		if l[i] == 0:
			index.append(i)
	sum = 0
	for i in range(len(index)):
		sum += 2 ** index[i]
	print(sum)


class Node:

	def __init__(self, value, parent, xor_count, left=None, right=None):
		self.value = value
		self.xor_count = xor_count
		self.parent = parent
		self.left = left
		self.right = right
		self.balance_factor = 0
		self.index = 0

	def __iter__(self):
		if self.left is not None:
			yield from self.left.__iter__()
		yield self.value
		if self.right is not None:
			yield from self.right.__iter__()

	def __repr__(self):
		return 'Node {val} with BF {bf}'.format(val=self.value, bf=self.balance_factor)

	def print_node(self, tab=0):
		if self.right is not None:
			self.right.print_node(tab + 2)
		print(' ' * tab + str(self.value))
		if self.left is not None:
			self.left.print_node(tab + 2)

class AvlTree:

	def __init__(self):
		self.root = None
		self.count = 0

	def __len__(self):
		return self.count

	def __iter__(self):
		yield from self.root.__iter__()

	def __getitem__(self, index):
		if index < 0:
			index += self.count

		def get_node(node):
			if index == node.index:
				return node
			elif index < node.index:
				if node.left is not None:
					return get_node(node.left)
				else:
					return None
			elif node.right is not None:
				return get_node(node.right)
			else:
				return None
		node = get_node(self.root)
		if node is not None:
			return node.value

	def print_tree(self):
		if self.root is not None:
			self.root.print_node()

	def add(self, value, xor_value):
		if self.root is None:
			self.root = Node(value=value, xor_count=xor_value, parent=None)
			self.count += 1
			return
		(parent, direction) = self._find_parent(value)
		if parent is None:
			return
		new_node = Node(value=value, xor_count=xor_value, parent=parent)
		if direction == 'L':
			parent.left = new_node
		else:
			parent.right = new_node
		self.modify_balance_factor(new_node)
		self.update_indexes()
		self.count += 1

	def modify_balance_factor(self, node):
		parent = node.parent
		if parent is None:
			return
		direction = 'L' if parent.value > node.value else 'R'
		if direction == 'L':
			parent.balance_factor += 1
		else:
			parent.balance_factor += -1
		if parent.balance_factor != 0:
			if parent.balance_factor in [-2, 2]:
				if parent.balance_factor == -2:
					parent_dir = 'R'
					if node.balance_factor == -1:
						node_dir = 'R'
					else:
						node_dir = 'L'
					general_dir = node_dir + parent_dir
					if general_dir == 'RR':
						self.left_rotation(node=node, parent=parent)
					elif general_dir == 'LR':
						self.right_rotation(node.left, node)
						self.left_rotation(node.parent, parent)
					else:
						raise Exception('Unexpected behavior!')
				else:
					parent_dir = 'L'
					if node.balance_factor == -1:
						node_dir = 'R'
					else:
						node_dir = 'L'
					general_dir = node_dir + parent_dir
					if general_dir == 'LL':
						self.right_rotation(node, parent)
					elif general_dir == 'RL':
						self.left_rotation(node.right, node)
						self.right_rotation(node.parent, parent)
					else:
						raise Exception('Unexpected behavior!')
			else:
				self.modify_balance_factor(parent)

	def left_rotation(self, node: Node, parent: Node):
		grand_parent = parent.parent
		old_left = node.left
		node.left = parent
		parent.right = old_left
		if old_left is not None:
			old_left.parent = parent
		parent.parent = node
		node.parent = grand_parent
		if grand_parent is None:
			self.root = node
		elif grand_parent.value > node.value:
			grand_parent.left = node
		else:
			grand_parent.right = node
		parent.balance_factor = 0
		node.balance_factor = 0

	def right_rotation(self, node: Node, parent: Node):
		grand_parent = parent.parent
		old_right = node.right
		node.right = parent
		parent.left = old_right
		if old_right is not None:
			old_right.parent = parent
		parent.parent = node
		node.parent = grand_parent
		if grand_parent is None:
			self.root = node
		elif grand_parent.value > node.value:
			grand_parent.left = node
		else:
			grand_parent.right = node
		parent.balance_factor = 0
		node.balance_factor = 0

	def _find_parent(self, value):

		def _find(root: Node):
			if root.value == value:
				return (None, None)
			if root.value > value:
				if root.left is not None:
					return _find(root.left)
				else:
					return (root, 'L')
			elif root.right is not None:
				return _find(root.right)
			else:
				return (root, 'R')
		return _find(self.root)

	def get_item(self, value):

		def dfs(node):
			if node.value == value:
				return node
			elif node.value > value:
				return dfs(node.left)
			elif node.value < value:
				return dfs(node.right)
		return dfs(self.root)

	def get_closest_element(self, value):
		closest_val = 0
		closest_node = self.root

		def dfs(node):
			nonlocal closest_val, closest_node
			if node.value == value:
				raise Exception()
			if node.value < value:
				if node.value > closest_val:
					closest_val = node.value
					closest_node = node
				if node.right is not None:
					dfs(node.right)
			elif node.value > value and node.left is not None:
				dfs(node.left)
		dfs(self.root)
		return closest_node

	def update_indexes(self):
		index = 0

		def update_index(node):
			nonlocal index
			if node.left is not None:
				update_index(node.left)
			node.index = index
			index += 1
			if node.right is not None:
				update_index(node.right)
		update_index(self.root)

	def range(self, start, end):
		items = []
		if self.root is None:
			return []

		def in_order_dfs(node):
			nonlocal items
			if node.value > start and node.left is not None:
				in_order_dfs(node.left)
			if end >= node.value >= start:
				items.append(node.value)
			if node.value < end and node.right is not None:
				in_order_dfs(node.right)
		in_order_dfs(self.root)
		return items
saved_x = AvlTree()
saved_x.add(1, 0)
saved_x.add(3, 0)
x_in_tree = {1, 3}
max = 10 ** 10
i = 3
while i <= max:
	i *= 2
	i += 1
	saved_x.add(i, 0)
	x_in_tree.add(i)

def main():
	query_count = int(input())
	for _ in range(query_count):
		x = int(input())
		if x in x_in_tree:
			print(0)
		else:
			closest_x = saved_x.get_closest_element(x).value
			diff = x - closest_x
			print(closest_x - diff + 1)
main()


q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	t = bin(x)[2:]
	t = list(map(int, t.strip()))
	for i in range(len(t)):
		if t[i] == 0:
			t[i] = 1
		else:
			t[i] = 0
	x = ''.join(map(str, t))
	x = int(x, 2)
	print(x)


import sys

def torevbin(n):
	b = ''
	while n > 0:
		b += str(n % 2)
		n //= 2
	return b
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	b = torevbin(x)
	ans = 0
	for i in range(len(b)):
		if b[i] == '0':
			ans += 2 ** i
	print(ans)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	if x == 0 or x == 1:
		print(0)
	else:
		bina = bin(x)[3:]
		l = len(bina)
		maxi = 2 ** l
		ans = maxi - int(bina, 2) - 1
		print(ans)


for _ in range(int(input())):
	n = int(input())
	s = bin(n)[2:][::-1]
	try:
		i = s.rindex('0') + 1
		k = 2 ** i - 1
		for j in range(0, i):
			if s[j] == '1':
				k -= 2 ** j
	except ValueError:
		k = 0
	print(k)


for _ in range(int(input())):
	(ans, t) = (0, 1)
	for c in bin(int(input()))[:2:-1]:
		ans += t * (c == '0')
		t <<= 1
	print(ans)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	s = 0
	c = 1
	while x > 0:
		if x & 1 == 0:
			s += c
		x = x >> 1
		c = c << 1
	print(s)


import sys
q = int(input().strip())
for a0 in range(q):
	d = int(input().strip())
	x = len(bin(d)) - 2
	print(2 ** x - 1 - d)


from random import randint
import sys

def naive(x):
	return sum((i ^ x > x for i in range(1, x)))

def f(x):
	res = 0
	(y, i) = (x, 0)
	while y:
		if not y & 1:
			res |= 1 << i
		y >>= 1
		i += 1
	return res
q = int(input().strip())
for a0 in range(q):
	x = int(sys.stdin.readline().strip())
	sys.stdout.write(str(f(x)) + '\n')


for _ in range(int(input())):
	print(sum((2 ** i for (i, c) in enumerate(bin(int(input()))[:1:-1]) if c == '0')))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	i = 1
	res = 0
	while x > 0:
		if not x & 1:
			res += 2 ** (i - 1)
		x = x >> 1
		i += 1
	print(res)


import sys
import math
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(2 ** int(1 + math.log(x, 2)) - x - 1)


from math import log
T = int(input())
for t in range(T):
	n = int(input())
	r = 0
	for i in range(int(log(n, 2)) + 1):
		if n & 2 ** i == 0:
			r += 2 ** i
	print(r)


q = int(input())
for _ in range(q):
	n = int(input())
	b = 1
	count = 0
	while b < n:
		if n & b == 0:
			count += b
		b <<= 1
	print(count)


import sys
q = int(input().strip())
x = []
for a0 in range(q):
	x.append(int(input().strip()))
for i in range(len(x)):
	print(int(''.join([str(1 - int(i)) for i in '{0:b}'.format(x[i])]), 2))


import sys
q = int(input().strip())
for index in range(q):
	result = 0
	x = int(input().strip())
	bin_rep = '{0:b}'.format(x)
	for i in range(1, len(bin_rep)):
		if bin_rep[i] == '0':
			result += 2 ** (len(bin_rep) - i - 1)
	print(result)


import sys

def Cur(x, less, greater):
	if less and greater:
		return 2 ** len(x)
	if not x:
		return 0
	ans = 0
	for i in '01':
		if not less and i > x[0]:
			continue
		if not greater and i == '1' and (x[0] == '1'):
			continue
		ans += Cur(x[1:], less or i < x[0], greater or i == '1')
	return ans

def Solve(x):
	x = bin(x)[2:]
	return Cur(x, False, False)
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(Solve(x))


import sys

def get_binary(n):
	bn = str(bin(n))[2:]
	return bn

def get_xor_vals(n):
	cnt = 0
	bn = get_binary(n)
	l = len(bn)
	for i in range(l):
		if bn[i] == '0':
			cnt = cnt + pow(2, l - 1 - i)
	return cnt
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(get_xor_vals(x))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	x_bin = bin(x)[2:]
	res = 0
	for i in range(1, len(x_bin)):
		if not int(x_bin[-i]):
			res += 2 ** (i - 1)
	print(res)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	count = 0
	bi = []
	while x != 0:
		bi.insert(0, x % 2)
		x = x // 2
	l = len(bi)
	for i in range(1, l):
		if bi[i] == 0:
			count += 2 ** (l - i - 1)
	print(count)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	l = list(bin(x)[2:])
	for i in range(len(l)):
		if l[i] == '0':
			l[i] = '1'
		else:
			l[i] = '0'
	print(int(''.join(l), 2))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	temp = x
	count = 0
	while temp != 0:
		temp = temp >> 1
		count += 1
	maxm = pow(2, count) - 1
	print(maxm ^ x)


from math import pow, ceil, log

def do_it(n):
	pow_of_2 = int(pow(2, ceil(log(n) / log(2))))
	return n - 1 if pow_of_2 == n else pow_of_2 - 1 - n
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(do_it(x))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	y = bin(x)[2:]
	z = '0b'
	for c in y:
		if c == '1':
			z = z + '0'
		else:
			z = z + '1'
	x = int(z, 2)
	print(x)


import math

def ans(x):
	i = 0
	count = 0
	while x:
		ans = x % 2
		if ans == 0:
			add = int(math.pow(2, i))
			count = count + add
		i = i + 1
		x = x // 2
	return count
import sys
l = []
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(ans(x))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	binary = bin(x)[2:][::-1]
	total = 0
	for (i, c) in enumerate(binary):
		if c == '0':
			total += 1 << i
	print(total)


import sys
q = int(input().strip())
for a0 in range(q):
	count = 0
	x = int(input().strip())
	a = bin(x)
	a = a[2:]
	a = a[::-1]
	c = -1
	for i in a:
		c = c + 1
		if i == '0':
			count = count + 2 ** c
	print(count)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	a = list(reversed(list(bin(x)[2:])))
	counter = 0
	for idx in range(len(a)):
		if int(a[idx]) == 0:
			counter += 2 ** idx
	print(counter)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(2 ** (len(bin(x)) - 2) - 1 - x)


import sys

def greater_a(x):
	result = 0
	for (i, d) in enumerate(bin(x)[2:]):
		if d == '0':
			result += 2 ** len(bin(x)[2 + i + 1:])
	return result
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	print(greater_a(x))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	binary = list(bin(x))[2:]
	binary.reverse()
	summ = 0
	for (idx, item) in enumerate(binary):
		if item == '0':
			summ += 2 ** idx
	print(summ)


def theGreatXOR(L, x):
	if x in L:
		return 0
	i = 0
	while L[i] < x and i < len(L) - 1:
		i += 1
	return L[i - 1] - (x - L[i - 1] - 1)
L = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183]
q = int(input().strip())
for a0 in range(q):
	print(theGreatXOR(L, int(input().strip())))


num_queries = int(input())
for each_query in range(num_queries):
	count = digits = 0
	num = int(input())
	while num > 0:
		if num & 1 == 0:
			count += 1 << digits
		digits += 1
		num >>= 1
	print(count)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	x = bin(x)
	l = [int(s) for s in x[2:]]
	ans = 0
	n = len(l)
	for i in range(n):
		if l[i] == 0:
			ans += 2 ** (n - i - 1)
	print(ans)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	b = bin(x)[2:]
	print(2 ** len(b) - 1 - x)


import sys
import math
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	mask = 2 ** math.ceil(math.log(x + 1, 2)) - 1
	print(x ^ mask)


q = int(input().strip())
for _ in range(q):
	x = int(input().strip())
	print((1 << x.bit_length()) - x - 1)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	count_a = 0
	bx = bin(x)[2:]
	for i in range(1, len(bx)):
		if bx[i] == '1':
			continue
		count_a += 2 ** (len(bx[1:]) - i)
	print(count_a)


import sys
q = int(input().strip())
for a0 in range(q):
	c = 0
	x = int(input().strip())
	for i in range(35):
		if 2 ** i - 1 >= x:
			break
	print(2 ** i - x - 1)


import sys
import math
vec = []
i = 34
while i >= 0:
	vec.append(int(math.pow(2, i)))
	i = i - 1
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	res = 0
	flag = False
	for pot in vec:
		if x - pot >= 0:
			x = x - pot
			flag = True
		elif flag:
			res = res + pot
	print(res)


import sys

def findXor(n):
	binary = '{0:b}'.format(n)
	count = 0
	for i in range(0, len(binary)):
		if binary[i] == '0':
			count += 2 ** (len(binary) - 1 - i)
	print(count)
q = int(input().strip())
for a in range(q):
	x = int(input().strip())
	findXor(x)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	ret = 0
	base = 1
	while x > 0:
		if x % 2 == 0:
			ret += base
		x = int(x / 2)
		base = base * 2
	print(ret)


q = int(input())
for i in range(q):
	x = int(input())
	s = 1
	while s < x:
		s *= 2
	if s != x:
		print(s - 1 - x)
	else:
		print(x - 1)


query = int(input())
for q in range(query):
	num = bin(int(input()))[2:][::-1]
	length = len(num)
	ans = 0
	for (cnt, x) in enumerate(num):
		if x == '0':
			ans += 2 ** cnt
	print(ans)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	mask = 1
	while mask < x:
		mask += mask + 1
	print(mask ^ x)


from operator import xor
q = int(input().strip())
for i in range(q):
	x = int(input().strip())
	bin_x = '{0:b}'.format(x)
	i_bin_x = list(reversed(bin_x))
	ans = 0
	for j in range(0, len(i_bin_x)):
		if i_bin_x[j] == '0':
			ans += pow(2, j)
	print(ans)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	a = 1
	sum2 = 0
	while x // a != 0:
		a = a * 2
	print(a - x - 1)


import sys
N = int(input())
for i in range(N):
	x = int(input())
	print(2 ** (len(bin(x)) - 2) - 1 ^ x)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	s = '{0:b}'.format(x)
	n = len(s)
	ans = 0
	for i in range(n):
		if s[i] == '0':
			ans += 2 ** (n - 1 - i)
	print(ans)


import sys

def es_potencia_de_dos(numero):
	if numero < 1:
		return False
	return 0 == numero & numero - 1
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	if x < 2:
		print(0)
	elif x & x - 1 is 0:
		print(x - 1)
	else:
		i = 1 << x.bit_length() - 1
		print(i - 1 - (x - i))


import sys
import math
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	esp = int(math.log(x, 2))
	power = 2 ** esp
	res = 2 * power - x - 1
	print(res)


import math
for _ in range(int(input().strip())):
	x = int(input().strip())
	mask = (1 << int(math.log2(x)) + 1) - 1
	print(x ^ mask)


import sys
import math
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	a = int(math.log(x, 2))
	b = math.ceil(math.log(x, 2))
	if a == b:
		b = b + 1
	d = int(math.pow(2, b)) - int(math.pow(2, a)) - 1
	print(d - x + int(math.pow(2, a)))


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	b = str(bin(x))[2:]
	m = ''
	for i in b:
		m += '1'
	print(int(m, 2) ^ x)


import sys
q = int(input().strip())
for a0 in range(q):
	x = int(input().strip())
	q = bin(x)[2:]
	c = ''
	for i in q:
		if i == '1':
			c += '0'
		else:
			c += '1'
	print(int(c, 2))