Read problem statements in [Russian] and [Mandarin Chinese].

Find the minimum integer K such that sum of bits present on odd positions in binary representation of all integers from 1 to K is greater than or equal to N.

The bits are enumerated from left to right starting from the leftmost set bit i.e. the most significant bit. For example, binary representation of 77 is 1001101. Bits present on 1^{st}, 3^{rd}, 5^{th} and 7^{th} positions in the binary representation are 1, 0, 1, 1 respectively. So sum of bits present on odd positions in binary representation of 77 is 1 + 0 + 1 + 1 = 3.

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of a single line of input, an integer N.

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

For each testcase, output in a single line the minimum possible value of K.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
2
6
100
----- Sample Output 1 ------ 
2
5
57
----- explanation 1 ------ 
-  In the first test case, binary representations of $1$ and $2$ are 1, 10. Sum of bits present on odd positions in the binary representation of $1$ and $2$ =  $1 + 1$ = $2$.
-  In the second test case, the binary representations of integers from $1$ to $5$ are 1, 10, 
11, 100, 101 respectively. So the sum of bits present on odd positions in binary 
representation of integers from $1$ to $5$ are $1, 1, 1, 1, 2$ respectively which makes a total of $6$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Sorting

Complete search

Dynamic programming

Mathematics


Solutions:
from math import ceil
for _ in range(int(input()) if True else 1):
	n = int(input())
	(alpha, omega) = (1, 10 ** 9)

	def getk(x, bits):
		ans = 0
		for j in range(1, bits, 2):
			i = bits - j - 1
			y = x // 2 ** i
			ans += y // 2 * 2 ** i
			if y % 2:
				ans += x % 2 ** i
		return ans

	def calc(x):
		ans = x
		for b in range(60):
			size = b + 1
			if x >= 2 ** size - 1:
				cnt = 2 ** b
				ans += cnt // 2 * (b // 2)
			else:
				left = x - 2 ** b + 1
				if left <= 0:
					break
				bits = b
				ans += getk(left, bits)
				break
		return ans
	while alpha < omega:
		x = (alpha + omega) // 2
		if calc(x) >= n:
			omega = x
		else:
			alpha = x + 1
	print(alpha)


from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	n = int(input())
	(alpha, omega) = (1, 10 ** 9)

	def getk(x, bits):
		ans = 0
		for j in range(1, bits, 2):
			i = bits - j - 1
			y = x // 2 ** i
			ans += y // 2 * 2 ** i
			if y % 2:
				ans += x % 2 ** i
		return ans

	def calc(x):
		ans = x
		for b in range(60):
			size = b + 1
			if x >= 2 ** size - 1:
				cnt = 2 ** b
				ans += cnt // 2 * (b // 2)
			else:
				left = x - 2 ** b + 1
				if left <= 0:
					break
				bits = b
				ans += getk(left, bits)
				break
		return ans
	while alpha < omega:
		x = (alpha + omega) // 2
		if calc(x) >= n:
			omega = x
		else:
			alpha = x + 1
	print(alpha)


for _ in range(int(input())):
	n = int(input())
	(alpha, omega) = (1, n)

	def getk(x, bits):
		ans = 0
		for j in range(1, bits, 2):
			i = bits - j - 1
			y = x // 2 ** i
			ans += y // 2 * 2 ** i
			if y % 2:
				ans += x % 2 ** i
		return ans

	def calc(x):
		ans = x
		for b in range(31):
			size = b + 1
			if x >= 2 ** size - 1:
				cnt = 2 ** b
				ans += cnt // 2 * (b // 2)
			else:
				left = x - 2 ** b + 1
				if left <= 0:
					break
				bits = b
				ans += getk(left, bits)
				break
		return ans
	while alpha < omega:
		x = (alpha + omega) // 2
		if calc(x) >= n:
			omega = x
		else:
			alpha = x + 1
	print(alpha)


def check(x):
	ans = 0
	for i in range(31):
		a = 1 << i
		if x < a:
			break
		if x == a:
			ans += 1
			break
		if x < a * 2 - 1:
			ans += x - a + 1
			f = 0
			s = 0
			if i & 1:
				s = 1
			e = i - 1
			while 1 << e & x == 0:
				e -= 1
			for j in range(s, e + 1, 2):
				y = (x - a + 1) // (1 << j)
				ans += y // 2 * (1 << j) + (x - a + 1) % (1 << j) * (y % 2)
		else:
			ans += a
			for j in range(i - 2, -1, -2):
				ans += a // 2
	return ans
for _ in range(int(input())):
	n = int(input())
	lo = 0
	hi = n
	while lo < hi:
		mid = (lo + hi) // 2
		if check(mid) < n:
			lo = mid + 1
		else:
			hi = mid
	print(lo)


import sys
import math

def read(lst=False):
	line = sys.stdin.readline().rstrip()
	if ' ' in line or lst:
		return map(int, line.split())
	return line

def util(n):
	if n == 1:
		return 1
	b = bin(n)[2:]
	l = len(b)
	total = memo[l - 1] + (n & (1 << l - 1) - 1) + (l & 1) * int(b[l - 1])
	for i in range(1, l - 1):
		total += (i + (l & 1)) // 2 * (1 << i - 1) * int(b[l - 1 - i])
		total += ((n & (1 << i) - 1) + 1) * int(b[l - 1 - i]) * (l - i & 1)
	return total

def binSearch(n, l, r):
	while l + 1 < r:
		mid = (l + r) // 2
		if util(mid) < n:
			l = mid
		else:
			r = mid
	return r

def solver(N):
	if N == 1:
		return 1
	for i in range(1, len(memo)):
		if memo[i] >= N:
			return binSearch(N, 1 << i - 1, 1 << i)
T = int(read())
(memo, num) = ([1], 0)
for i in range(1, 30):
	memo.append(2 * memo[-1] + num)
	if not i & 1:
		num = 4 * num + 2
for t in range(T):
	N = int(read())
	print(solver(N))
sys.exit()