Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given an integer $C$. Let $d$ be the smallest integer such that $2^{d}$ is strictly greater than $C$.

Consider all pairs of non-negative integers $(A,B)$ such that $A,B < 2^{d}$ and $A \oplus B = C$ ($\oplus$ denotes the bitwise XOR operation). Find the maximum value of $A \cdot B$ over all these pairs.

------  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 a single integer $C$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum possible product $A \cdot B$.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ C ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ C ≤ 10^{3}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2

13

10
----- Sample Output 1 ------ 
70

91
----- explanation 1 ------ 
Example case 1: The binary representation of $13$ is "1101". We can use $A = 10$ ("1010" in binary) and $B = 7$ ("0111" in binary). This gives us the product $70$. No other valid pair $(A, B)$ can give us a larger product.

Example case 2: The binary representation of $10$ is "1010". We can use $A = 13$ ("1101") and $B = 7$ ("0111"). This gives us the maximum product $91$.

Difficulty: MEDIUM
Tags: Bit manipulation

Constructive algorithms

Greedy algorithms

Mathematics

Ad-hoc
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
def solve():
	num = int(input())
	tmp = bin(num)[2:]
	a = ''
	b = ''
	flag = True
	for i in tmp:
		if i == '1':
			if flag:
				a += '1'
				b += '0'
				flag = False
			else:
				a += '0'
				b += '1'
		else:
			a += '1'
			b += '1'
	print(int(a, 2) * int(b, 2))
t = int(input())
while t != 0:
	t -= 1
	solve()


def largest(i):
	k = 2
	while k <= i:
		k = k * 2
	return k
i = int(input())
listk = []
for _ in range(i):
	listno = []
	kk = int(input())
	max = 0
	ls = largest(kk)
	no = ''
	for k in range(len(format(kk, 'b'))):
		if k == 0:
			no = '1'
		elif str(format(kk, 'b'))[k] == '0':
			no = no + '1'
		elif str(format(kk, 'b'))[k] == '1':
			no = no + '0'
	max = int(no, 2) * (int(no, 2) ^ kk)
	listk.append(max)
for ele in listk:
	print(ele)


def Power(n):
	(ans, x) = (1, 2)
	while n != 0:
		if n & 1 == 1:
			ans = ans * x
		n = n >> 1
		x = x * x
	return ans
for _ in range(int(input())):
	c = int(input())
	(s1, s2, d) = (0, 0, 0)
	for i in range(31, -1, -1):
		if c >> i & 1 == 1 and s1 == 0:
			s1 = s1 + Power(i)
			d = i
		elif c >> i & 1 == 1 and s1 != 0:
			s2 = s2 + Power(i)
		if c >> i & 1 == 0 and s1 != 0:
			s1 = s1 + Power(i)
			s2 = s2 + Power(i)
	if s1 >= Power(d + 1):
		s1 = s1 - 1
	if s2 >= Power(d + 1):
		s2 = s2 - 1
	print(s1 * s2)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t:
	t -= 1
	c = int(input())
	i = 0
	while 1 << i <= c:
		i += 1
	a = 0
	b = 0
	flag = True
	for j in range(i - 1, -1, -1):
		if c & 1 << j == 0:
			a |= 1 << j
			b |= 1 << j
		elif flag:
			b |= 1 << j
			flag = False
		else:
			a |= 1 << j
	print(a * b)


for i in range(int(input())):
	n = int(input())
	b = bin(n)[2:]
	p = ''
	q = ''
	i = 0
	t = 'p'
	while i < len(b):
		if b[i] == '1':
			p1 = p + '1'
			q1 = q + '0'
			p2 = p + '0'
			q2 = q + '1'
			if int(p1, 2) * int(q1, 2) > int(p2, 2) * int(q2, 2):
				p = p1
				q = q1
			else:
				p = p2
				q = q2
		else:
			p += '1'
			q += '1'
		i += 1
	print(int(p, 2) * int(q, 2))


import math
for _ in range(int(input())):
	c = int(input())
	d = int(math.log(c, 2))
	a = 2 ** d - 1
	b = c ^ a
	print(b * a)


from math import log
for _ in range(int(input())):
	c = int(input())
	k = int(log(c, 2))
	a = pow(2, k) - 1
	b = c ^ a
	print(a * b)


T = int(input())
for t in range(T):
	C = bin(int(input()))
	if C == '0b1':
		print(0)
	else:
		A = '0b1'
		B = '0b'
		for i in range(3, len(C)):
			B += '1'
			if C[i] == '1':
				A += '0'
			else:
				A += '1'
		print(int(A, 2) * int(B, 2))


t = int(input())
for u in range(t):
	n = int(input())
	a = b = 0
	i = 0
	while n > 1:
		r = n % 2
		if r:
			b += 2 ** i
		else:
			a += 2 ** i
			b += 2 ** i
		n //= 2
		i += 1
	a += 2 ** i
	print(a * b)


import math
t = int(input())
while t:
	t -= 1
	c = int(input())
	n = int(math.log(c) / math.log(2))
	n += 1
	j = 1
	k = -1
	a = 0
	b = 0
	for i in range(n):
		if c % 2:
			b += j
			k = j
		else:
			a += j
			b += j
		j *= 2
		c //= 2
	if k != -1:
		b -= k
		a += k
	print(a * b)


def toBin(n):
	return bin(n).replace('0b', ' ')

def solve(n):
	s = str(toBin(n))
	a = []
	b = []
	for i in range(len(s)):
		if s[i] == '1':
			if a.count('1') == 0:
				a.append('1')
				b.append('0')
			else:
				b.append('1')
				a.append('0')
		elif s[i] == '0':
			a.append('1')
			b.append('1')
	a = ''.join(a)
	b = ''.join(b)
	a = int(a, 2)
	b = int(b, 2)
	return a * b
for _ in range(int(input())):
	c = int(input())
	print(solve(c))


from math import log
for _ in range(int(input())):
	A = B = 0
	C = int(input())
	bits = int(log(C) / log(2)) + 1
	bin_str = ''
	for _ in range(bits):
		remainder = str(C % 2)
		bin_str += remainder
		C = int(C / 2)
	bin_str = bin_str[::-1]
	taken = False
	for i in range(bits):
		if bin_str[i] == '0':
			A += 2 ** (bits - 1 - i)
			B += 2 ** (bits - 1 - i)
		elif taken is False:
			taken = True
			A += 2 ** (bits - 1 - i)
		else:
			B += 2 ** (bits - 1 - i)
	print(A * B)


for _ in range(int(input())):
	n = int(input())
	x = bin(n).replace('0b', '')
	res = pow(2, len(x))
	res //= 2
	print((res - 1) * (n ^ res - 1))


t = int(input())
for _ in range(t):
	num = int(input())
	a = 0
	b = 0
	count = 0
	while num != 0:
		if num & 1:
			if num >> 1 == 0:
				a |= 1 << count
			else:
				b |= 1 << count
		else:
			a |= 1 << count
			b |= 1 << count
		num >>= 1
		count += 1
	print(a * b)


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	a = 0
	b = 0
	count = 0
	while num != 0:
		if num & 1:
			if num >> 1 == 0:
				a |= 1 << count
			else:
				b |= 1 << count
		else:
			a |= 1 << count
			b |= 1 << count
		num >>= 1
		count += 1
	print(a * b)


import sys
import math
from functools import cmp_to_key
from collections import OrderedDict
sys.setrecursionlimit(10 ** 9)

def solve():
	for t in range(int(input())):
		c = int(input())
		n = int(math.log2(c))
		a = 0
		b = 0
		flag = True
		for i in range(n, -1, -1):
			if c & 1 << i == 0:
				a += 1 << i
				b += 1 << i
			elif flag:
				a += 1 << i
				flag = False
			else:
				b += 1 << i
		print(a * b)
solve()


for _ in range(int(input())):
	s = int(input())
	s = bin(s).replace('0b', '')
	a = ''
	b = ''
	count = 0
	for i in s:
		if i == '0':
			a += '1'
			b += '1'
		elif i == '1':
			if count == 0:
				a += '1'
				b += '0'
				count += 1
			else:
				b += '1'
				a += '0'
	print(int(a, 2) * int(b, 2))


t = int(input())
while t > 0:
	c = 0
	n = int(input())
	m = n
	while m != 0:
		m = m >> 1
		c += 1
	a_ = 0
	b_ = 0
	flag = False
	for i in range(c - 1, -1, -1):
		mask = 1 << i
		val = n & mask
		if val == 0:
			a_ = a_ | 1 << i
			b_ = b_ | 1 << i
		elif flag == False:
			a_ = a_ | 1 << i
			flag = True
		else:
			b_ = b_ | 1 << i
	print(a_ * b_)
	t -= 1


for _ in range(int(input())):
	c = int(input())
	d = len(bin(c)) - 2
	x = 2 ** (d - 1) - 1
	print(x * (c ^ x))


for _ in range(int(input())):
	n = int(input())
	x = bin(n).replace('0b', '')
	p = 1 << len(x) + 1 - 1
	p //= 2
	print((p - 1) * (n ^ p - 1))


import math

def function(C, A, B, index, hashTable):
	n = math.floor(math.log2(C))
	z = (1 << n) - 1
	return z * (z ^ C)

def main():
	T = int(input())
	for _ in range(T):
		C = int(input())
		val = function(C, 0, 0, 0, {})
		print(val)
main()


def main():
	T = int(input())
	for counter in range(T):
		ans = 0
		a = ''
		b = ''
		c = int(input())
		cbin = bin(c)[2:]
		d = len(cbin)
		cbin = str(cbin)
		countera = 0
		counterb = 0
		for i in range(len(cbin)):
			if cbin[i] == '0':
				a += '1'
				b += '1'
			elif countera > counterb:
				a += '0'
				b += '1'
				counterb += 2 ** (d - i)
			else:
				a += '1'
				b += '0'
				countera += 2 ** (d - i)
		ans = int(a, 2) * int(b, 2)
		print(ans)
main()


from math import *
for _ in range(int(input())):
	c = int(input())
	k = 1 << int(log2(c))
	e = (k << 1) - 1
	print((e ^ k) * (e ^ k ^ c))


try:
	for i in range(int(input())):
		n = int(input())
		bi = bin(n).replace('0b', '')
		a = 2 ** len(bi) // 2
		l = 2 ** len(bi) - 1
		b = l - (n - a)
		a -= 1
		print(a * b)
except Exception as e:
	print(e)


t = int(input())
for i in range(t):
	n = int(input())
	a = ''
	while n >= 1:
		a = str(n % 2) + a
		n = n // 2
	c = 1
	p = ''
	q = ''
	for i in a:
		if i == '1':
			if c == 1:
				p = p + '1'
				q = q + '0'
				c = c + 1
			else:
				q = q + '1'
				p = p + '0'
		else:
			p = p + '1'
			q = q + '1'
	i = 0
	x = 0
	while True:
		if p == '':
			break
		else:
			x = x + int(p[-1]) * 2 ** i
			p = p[0:-1]
			i = i + 1
	j = 0
	y = 0
	while True:
		if q == '':
			break
		else:
			y = y + int(q[-1]) * 2 ** j
			q = q[0:-1]
			j = j + 1
	print(x * y)


for _ in range(int(input())):
	n = int(input())
	binary = bin(n)
	binary = binary[2:]
	a = '1'
	b = '0'
	for i in range(1, len(binary)):
		if binary[i] == '1':
			b += '1'
			a += '0'
		else:
			a += '1'
			b += '1'
	print(int(a, 2) * int(b, 2))


for _ in range(int(input())):
	n = int(input())
	binary = bin(n)
	binary = binary[2:]
	a = ''
	b = ''
	for i in range(len(binary)):
		if binary[i] == '1':
			temp_1 = a + '1'
			temp_2 = b + '0'
			temp_3 = a + '0'
			temp_4 = b + '1'
			if int(temp_1, 2) * int(temp_2, 2) > int(temp_3, 2) * int(temp_4, 2):
				a = temp_1
				b = temp_2
			else:
				a = temp_3
				b = temp_4
		else:
			a += '1'
			b += '1'
	print(int(a, 2) * int(b, 2))


import math
t = int(input())
for i in range(t):
	x = int(input())
	c = bin(x).replace('0b', ' ')
	a = int(math.log2(x)) + 1
	b = '1' * a
	b = int(b, 2)
	c = int(c, 2)
	d = b ^ c
	d = d | 1 << a - 1
	b = b & ~(1 << a - 1)
	print(b * d)


t = int(input())
for _ in range(t):
	n = int(input())
	b = '{0:b}'.format(n)
	b = list(b)
	x = ''
	y = ''
	flag = False
	for i in range(len(b)):
		if not flag and b[i] == '1':
			x += '1'
			y += '0'
			flag = True
		elif b[i] == '1':
			x += '0'
			y += '1'
		else:
			x += '1'
			y += '1'
	res_1 = 0
	res_2 = 0
	for i in range(len(x)):
		res_1 += int(x[i]) * 2 ** (len(x) - (i + 1))
		res_2 += int(y[i]) * 2 ** (len(y) - (i + 1))
	print(res_1 * res_2)


for _ in range(int(input())):
	n = int(input())
	bi = bin(n)[2:]
	f = False
	a = ''
	b = ''
	for i in range(len(bi)):
		if not f and bi[i] == '1':
			a += '1'
			b += '0'
			f = True
		elif bi[i] == '1':
			a += '0'
			b += '1'
		else:
			a += '1'
			b += '1'
	print(int(a, 2) * int(b, 2))


for _ in range(int(input())):
	c = int(input())
	b = bin(c)[2:]
	o = []
	for i in range(len(b)):
		if i == 0:
			o.append('1')
		elif b[i] == '1':
			o.append('0')
		else:
			o.append('1')
	n1 = int(''.join(o), 2)
	n2 = c ^ n1
	print(n1 * n2)


t = int(input())
for i in range(t):
	c = int(input())
	msb = 0
	for i in range(32, -1, -1):
		if 1 << i & c:
			msb = i
			break
	(a, b) = (0, 0)
	f = 1
	for i in range(msb, -1, -1):
		if 1 << i & c:
			if f:
				a |= 1 << i
				f = 0
			else:
				b |= 1 << i
		else:
			a |= 1 << i
			b |= 1 << i
	print(a * b)


p = int(input())
for i in range(p):
	c = int(input())
	w = bin(c)[2:]
	a = ''
	b = ''
	se = False
	for i in range(len(w)):
		if not se and w[i] == '1':
			a += '1'
			b += '0'
			se = True
		elif w[i] == '1':
			a += '0'
			b += '1'
		else:
			a += '1'
			b += '1'
	print(int(a, 2) * int(b, 2))


import math
for i in range(int(input())):
	n = int(input())
	r = bin(n)
	x = len(r) - 2
	z = math.pow(2, x)
	g = math.pow(2, x - 1)
	z = int(z)
	g = int(g)
	d = n - (g - 1)
	b = z - d
	a = g - 1
	print(a * b)


for _ in range(int(input())):
	c = int(input())
	binary = bin(c).replace('0b', '')
	a = 0
	b = 0
	for i in range(len(binary)):
		if binary[i] == '0':
			a += 2 ** (len(binary) - i - 1)
			b += 2 ** (len(binary) - i - 1)
		elif i == 0:
			a += 2 ** (len(binary) - 1)
		else:
			b += 2 ** (len(binary) - 1 - i)
	print(a * b)


T = int(input())
for _ in range(T):
	C = int(input())
	(A, B) = ('1', '0')
	for i in bin(C)[3:]:
		if i == '0':
			A += '1'
			B += '1'
		else:
			B += '1'
			A += '0'
	print(int(A, 2) * int(B, 2))


t = int(input())
for _ in range(t):
	n = int(input())
	n = bin(n).replace('0b', '')
	leng = len(n)
	a = str()
	b = str()
	a1 = 1
	for i in range(leng):
		if n[i] == '1' and a1 == 1:
			a = a + '1'
			b = b + '0'
			a1 = 0
		elif n[i] == '0':
			a = a + '1'
			b = b + '1'
		elif n[i] == '1':
			a = a + '0'
			b = b + '1'
	a = '0b' + a
	b = '0b' + b
	a = int(a, 2)
	b = int(b, 2)
	print(a * b)


def decimalToBinary(n):
	return bin(n).replace('0b', '')
for i in range(int(input())):
	n = int(input())
	binary = decimalToBinary(n)
	a1 = 0
	a2 = 0
	for i in range(len(binary)):
		if binary[i] == '0':
			a1 = a1 * 2 + 1
			a2 = a2 * 2 + 1
		if binary[i] == '1':
			if i == 0:
				a1 = a1 * 2 + 1
				a2 = a2 * 2
			elif a1 > a2:
				a1 = a1 * 2
				a2 = a2 * 2 + 1
			else:
				a1 = a1 * 2 + 1
				a2 = a2 * 2
	print(a1 * a2)


for _ in range(int(input())):
	y = int(input())
	b = bin(y).replace('0b', '')
	b = str(b)
	ans = ['1']
	for j in range(1, len(b)):
		if b[j] == '0':
			ans.append('1')
		else:
			ans.append('0')
	a = ''.join(ans)
	a = int(a, 2)
	b = int(b, 2)
	r = a ^ b
	print(a * r)


for i in range(int(input())):
	c = int(input())
	b = bin(c).replace('0b', '')
	b = str(b)
	a = '1'
	r = '0'
	for j in range(1, len(b)):
		if b[j] == '0':
			a += '1'
			r += '1'
		else:
			a += '0'
			r += '1'
	a = int(a, 2)
	b = int(b, 2)
	r = int(r, 2)
	print(a * r)


for _ in range(int(input())):
	n = int(input())
	s = bin(n)[2:]
	l = len(s)
	(x, y) = ('', '')
	for i in range(l):
		if i == 0:
			if s[i] == '1':
				x += '1'
				y += '0'
			else:
				x += '1'
				y += '1'
		elif s[i] == '1':
			x += '0'
			y += '1'
		else:
			x += '1'
			y += '1'
	x = int(x, 2)
	y = int(y, 2)
	print(x * y)


for t in range(int(input())):
	c = int(input())
	a = 0
	b = 0
	msbc = 0
	for i in range(31, -1, -1):
		if 1 << i & c:
			msbc = i
			break
	flag = True
	for i in range(msbc, -1, -1):
		if 1 << i & c:
			if flag:
				a |= 1 << i
				flag = False
			else:
				b |= 1 << i
		else:
			a |= 1 << i
			b |= 1 << i
	print(a * b)


for _ in range(int(input())):
	n = int(input())
	c = bin(n).replace('0b', '')
	a = ''
	b = ''
	c = list(c)
	f = 1
	for i in range(len(c)):
		if c[i] == '1' and f == 1:
			a += '1'
			b += '0'
			f = 0
		elif c[i] == '1' and f == 0:
			b += '1'
			a += '0'
		elif c[i] == '0':
			a += '1'
			b += '1'
	print(int(a, 2) * int(b, 2))


t = int(input())
for _ in range(t):
	C = int(input())
	d = len(bin(C)) - 2
	A = 2 ** d - 1 ^ C
	B = A
	A |= 2 ** (d - 1)
	C ^= 2 ** (d - 1)
	B = B | C
	print(A * B)


import math
for i in range(int(input())):
	N = int(input())
	p = math.floor(math.log2(N))
	p = 2 ** p - 1
	k = p ^ N
	print(k * p)


for i in range(int(input())):
	c = int(input())
	a = 0
	b = 0
	t = 0
	for j in range(32, -1, -1):
		r = c & 1 << j
		if r > 0:
			if t == 0:
				t = 1
			if a < b:
				a += r
			else:
				b += r
		elif t != 0:
			a += 1 << j
			b += 1 << j
	print(a * b)


T = int(input())
for i in range(T):
	n = int(input())
	s = bin(n)[2:]
	p = 0
	sec = 0
	x = 0
	for z in range(len(s) - 1, -1, -1):
		if s[z] == '0':
			p = p + 2 ** x
			sec = sec + 2 ** x
			x += 1
		else:
			if z == 0:
				p = p + 2 ** x
			else:
				sec = sec + 2 ** x
			x += 1
	print(p * sec)


def decimalToBinary(n):
	return bin(n).replace('0b', '')
case = int(input())
for i in range(case):
	c = int(input())
	n = str(decimalToBinary(c))
	a = [0] * len(n)
	b = [0] * len(n)
	a[0] = 1
	for i in range(1, len(n)):
		if n[i] == '0':
			a[i] = 1
			b[i] = 1
		else:
			b[i] = 1
	k = len(n) - 1
	A = 0
	B = 0
	i = 0
	while k >= 0:
		A += 2 ** k * a[i]
		B += 2 ** k * b[i]
		i += 1
		k -= 1
	print(A * B)


import sys
import math
from collections import defaultdict, Counter, deque
from heapq import heapify, heappop, heappush

class Solution:

	def __init__(self, n):
		self.n = n

	def numOfDigits(self, n):
		d = 0
		while n:
			(d, n) = (d + 1, n >> 1)
		return d

	def exec(self):
		a = b = 0
		d = self.numOfDigits(self.n)
		for i in range(d - 1, -1, -1):
			if self.n & 1 << i:
				c = a | 1 << i
				d = b | 1 << i
				if c * b > a * d:
					a = c
				else:
					b = d
			else:
				a |= 1 << i
				b |= 1 << i
		print(a * b)
test_cases = int(input())
for t in range(1, test_cases + 1):
	n = int(input())
	Solution(n).exec()


import math
for _ in range(int(input())):
	p = int(input())
	q = int(math.log(p, 2))
	a = 2 ** q - 1
	b = p ^ a
	print(a * b)


import math
for _ in range(int(input())):
	x = int(input())
	t = int(math.log(x, 2))
	a = 2 ** t - 1
	b = x ^ a
	print(a * b)


for _ in range(int(input())):
	x = int(input())
	a = '1'
	b = '0'
	x = bin(x)[2:]
	for i in x[1:]:
		if i == '0':
			a += '1'
			b += '1'
		else:
			b += '1'
			a += '0'
	print(int(a, 2) * int(b, 2))


for _ in range(int(input())):
	c = int(input())
	id = 0
	a = 0
	b = 0
	flag = 1
	for i in range(31, -1, -1):
		if c & 1 << i:
			id = i
			break
	for i in range(id, -1, -1):
		if c & 1 << i:
			if flag == 1:
				a = a | 1 << i
				flag = 0
			else:
				b = b | 1 << i
		else:
			a = a | 1 << i
			b = b | 1 << i
	print(a * b)


t = int(input())
for i in range(t):
	c = int(input())
	a = 0
	b = 0
	f = 1
	id = 0
	for i in range(31, -1, -1):
		if c & 1 << i:
			id = i
			break
	for i in range(id, -1, -1):
		if c & 1 << i:
			if f == 1:
				a = a | 1 << i
				f = 0
			else:
				b = b | 1 << i
		else:
			a = a | 1 << i
			b = b | 1 << i
	print(a * b)


testcases = int(input())
for i in range(testcases):
	C = int(input())
	temp = bin(C).replace('0b', '')
	x = '0'
	y = '1'
	z = len(temp)
	for k in range(1, z):
		if temp[k] == '1':
			x = x + '1'
			y = y + '0'
		else:
			x = x + '1'
			y = y + '1'
	A = int(x, 2)
	B = int(y, 2)
	print(A * B)


for _ in range(int(input().strip())):
	C = int(input().strip())
	bin_c = bin(C)[2:]
	out_bin_A = ['1'] + ['0'] * (len(bin_c) - 1)
	out_bin_B = ['0'] * len(bin_c)
	for (idx, bit) in enumerate(bin_c[1:], 1):
		if bit == '0':
			out_bin_A[idx] = '1'
			out_bin_B[idx] = '1'
		elif bit == '1':
			out_bin_B[idx] = '1'
	print(int(''.join(out_bin_A), 2) * int(''.join(out_bin_B), 2))


from math import log

def solve(n):
	width = int(log(n, 2)) + 1
	a = 2 ** (width - 1) - 1
	b = a ^ n
	return a * b
for _ in range(int(input())):
	c = int(input())
	print(solve(c))


ass = int(input())
for i in range(ass):
	bn = int(input())
	bn = bin(bn)[2:]
	r = len(bn)
	bn = bn[1:]
	a = ['1'] + ['0' if i == '1' else '1' for i in bn]
	b = ['0'] + ['1'] * (r - 1)
	a = ''.join(a)
	b = ''.join(b)
	c = int(a, 2) * int(b, 2)
	print(c)


for _ in range(int(input())):
	c = int(input())
	s = str(bin(c))[2:]
	(s1, s2) = ('', '')
	k = True
	for i in s:
		if i == '0':
			s1 += '1'
			s2 += '1'
		elif k:
			s1 += '1'
			s2 += '0'
			k = False
		else:
			s1 += '0'
			s2 += '1'
	a = 0
	for i in range(len(s1)):
		a += int(s1[::-1][i]) * 2 ** i
	b = 0
	for i in range(len(s2)):
		b += int(s2[::-1][i]) * 2 ** i
	print(a * b)


for _ in range(int(input())):
	c = int(input())
	a = b = 0
	flag = False
	for i in range(32, -1, -1):
		if flag:
			if c & 1 << i > 0:
				a |= 1 << i
			else:
				a |= 1 << i
				b |= 1 << i
		elif c & 1 << i > 0:
			flag = True
			b = 1 << i
	print(a * b)


def decimalToBinary(n):
	return bin(n).replace('0b', '')
t = int(input())
for z in range(t):
	n = int(input())
	l = list(decimalToBinary(n))
	s = ''
	s1 = ''
	for i in range(len(l) - 1, 0, -1):
		if l[i] == '1':
			s = s + '1'
			s1 = s1 + '0'
		else:
			s += '1'
			s1 = s1 + '1'
	if l[0] == '1':
		s += '0'
		s1 += '1'
	else:
		s += '0'
		s1 += '0'
	print(int(s[::-1], 2) * int(s1[::-1], 2))


t = int(input())
for _ in range(t):
	n = int(input())
	bi_num = bin(n)[2:]
	(a, b) = (1, 0)
	for i in bi_num[1:]:
		if i == '1':
			(a, b) = (2 * a, 2 * b + 1)
		else:
			(a, b) = (2 * a + 1, 2 * b + 1)
	print(a * b)