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

In Chefland, there are $N$ cities (numbered $1$ through $N$). Initially, there are no roads between them. The Mayor of Chefland has ordered engineers to build roads across Chefland in such a way that each city is reachable from all other cities.

For each pair of distinct cities $i$ and $j$, the cost of building a road between these cities is equal to ($i \wedge j$), where $\wedge$ denotes the bitwise AND operation. However, leaders of the cities have a weird condition ― they only allow roads with positive costs to be built from their cities.

Help the Mayor find the minimum cost of building roads in the required way or determine that it is impossible.

------  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 $N$. 

------  Output ------
For each test case, print a single line containing one integer ― the minimum cost of building the roads or $-1$ if it is impossible.

------  Constraints ------
$1 ≤ T ≤ 2 \cdot 10^{5}$
$2 ≤ N ≤ 10^{9}$

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

3

5
----- Sample Output 1 ------ 
3

8
----- explanation 1 ------ 
Example case 1: We can connect city $1$ with city $3$ by a road with cost $1$ and city $3$ with city $2$ by a road with cost $2$.

Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Bit manipulation

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	if n & n - 1 == 0:
		print(-1)
	else:
		count = (n - 1) // 2
		cost = 2
		while cost < n:
			count += (n - cost) // (2 * cost) * cost + cost
			cost <<= 1
		print(count)


l = [2 ** x for x in range(32)]
t = int(input())
for i in range(t):
	n = int(input())
	x = 30
	v = 0
	f = 1
	while x > 0:
		if l[x] == n:
			print(-1)
			f = 0
			break
		v += l[x] * (n // l[x] - n // l[x + 1])
		x -= 1
	if n % 2 == 0:
		v += n // 2 - 1
	else:
		v += n // 2
	if f != 0:
		print(v)


li = [pow(2, x) for x in range(32)]
T = int(input())
for i in range(T):
	n = int(input())
	x = 30
	val = 0
	flag = 1
	prev = n // li[x + 1]
	while x > 0:
		if li[x] == n:
			print(-1)
			flag = 0
			break
		now = n // li[x]
		val = val + li[x] * (now - prev)
		prev = now
		x -= 1
	if n % 2 == 0:
		val = val + n // 2 - 1
	else:
		val = val + n // 2
	if flag != 0:
		print(val)


case = int(input())
for r in range(case):
	n = int(input())
	if n == 2:
		print(-1)
		continue
	if n & n - 1 == 0:
		print(-1)
		continue
	summ = n - 1 - n // 2
	pw = 1
	while pow(2, pw) <= n:
		pw += 1
	for i in range(1, pw):
		nu = pow(2, i)
		summ += ((n - nu) // (2 * nu) + 1) * nu
	print(summ)


T = int(input())
for i in range(T):
	n = int(input())
	ans = -1
	curr = 1
	while True:
		if curr == n:
			ans = -1
			break
		elif curr > n:
			break
		ans += curr * ((n + curr) // (2 * curr))
		curr *= 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	ans = -1
	curr = 1
	while True:
		if curr == n:
			ans = -1
			break
		elif curr > n:
			break
		ans += curr * ((n + curr) // (2 * curr))
		curr *= 2
	print(ans)


import sys
import math

def fout(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fin():
	return sys.stdin.readline().strip()

def dfsutil(curr):
	visit[curr] = True
	for item in graph[curr]:
		if not visit[item]:
			graph[item].remove(curr)
			dfs(item)

def dfs(start, end):
	for i in range(start, end + 1):
		if not visit[i]:
			dfsutil(i)

def bfs(start):
	q = deque([start])
	visit[start] = True
	while len(q) > 0:
		curr = q.popleft()
		for item in graph[curr]:
			if not visit[curr]:
				q.append(item)
				visit[item] = True
epsilon = 10 ** (-6)

def check():
	pass

def bin(start, end):
	ans = end
	while end - start > epsilon:
		mid = start + (end - start) // 2
		if check(mid):
			ans = mid
			start = mid + epsilon
		else:
			end = mid - epsilon
	return ans
t = int(fin())
while t > 0:
	t -= 1
	n = int(fin())
	if n & n - 1 == 0:
		print(-1)
		continue
	ans = n // 2 - 1
	if n % 2:
		ans += 1
	bits = math.ceil(math.log(n, 2))
	for i in range(1, bits):
		temp = 2 ** i
		ans += temp * ((n + temp) // (temp * 2) - 1)
		ans += temp
	print(ans)


t = int(input())
arr = [2 ** i for i in range(1, 32)]
for _ in range(t):
	d = int(input())
	if d in arr:
		print(-1)
	elif d == 3:
		print(3)
	else:
		sum = (d - 1) // 2
		i = 2
		while i < d:
			m = d // i
			sum += (m + 1) // 2 * i
			i = i * 2
		print(sum)


def land(n):
	sum = (n + 1) // 2
	k = 2
	while True:
		c = (n + k) // (2 * k)
		if c == 0:
			return sum - 1
		sum += c * k
		k = k * 2
from math import log2
for _ in range(int(input())):
	n = int(input())
	if pow(2, int(log2(n))) == n:
		print(-1)
	else:
		print(land(n))


from math import log2
for _ in range(int(input())):
	n = int(input())
	if pow(2, int(log2(n))) == n:
		print('-1')
	else:
		ans = 0
		i = 1
		while i < n:
			ans += (n - i) // (i << 1) * i
			i <<= 1
		i = 2
		while i < n:
			ans += i
			i <<= 1
		print(ans)


t = int(input())
ans = []
for ti in range(t):
	n = int(input())
	ansi = 0
	lsb = 1
	fake_n = n
	while fake_n % 2 == 0:
		fake_n //= 2
		lsb *= 2
	if lsb == n:
		ans.append(-1)
	else:
		fake_n = n
		msb = 1
		while fake_n > 1:
			msb *= 2
			fake_n //= 2
		ansi += (n + 1) // 2 - 1
		x = 2
		while x <= msb:
			y = (n - x) // (2 * x) + 1
			ansi += y * x
			x *= 2
		ans.append(ansi)
for ansi in ans:
	print(ansi)


t = int(input())
for _ in range(t):
	n = int(input())
	if n & n - 1 == 0:
		print(-1)
	else:
		cost = 0
		oddCtr = (n + 1) // 2
		cost += oddCtr - 1
		curCost = 2
		while curCost < n:
			cost += (n - curCost) // (curCost * 2) * curCost + curCost
			curCost = curCost << 1
		print(cost)


from math import log2, ceil

def solve(N):
	if not N & N - 1:
		return -1
	res = 0
	bits = int(ceil(log2(N + 1)))
	for b in range(bits):
		size = (N - (1 << b)) // (1 << b + 1) + 1
		res += (1 << b) * (size - 1)
		if b < bits - 1:
			res += 1 << b + 1
	return res

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		N = int(stdin.readline().strip())
		out = solve(N)
		print(out)
main()


from math import floor, log2

def checkPower(n):
	cur = 1
	while cur < n:
		cur *= 2
	if n == 1:
		return True
	res = cur - n
	if res:
		return True
	return False

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		if checkPower(n):
			res = floor(log2(n))
			totalCost = 0
			f = False
			for i in range(res + 1):
				cost = 2 ** i
				v = (n + cost) // (cost * 2)
				totalCost += (v - 1) * cost
				if f:
					totalCost += cost
				f = True
			print(totalCost)
		else:
			print(-1)
main()


import math

def get_ans(n):
	if n & n - 1 == 0:
		print(-1)
		return
	ans = 0
	for i in range(math.floor(math.log2(n)) + 1):
		s = pow(2, i)
		l = (n + s) // (s * 2)
		ans += (l - 1) * s
		if i != 0:
			ans += s & s + 1
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	get_ans(n)


import math
for _ in range(int(input())):
	n = int(input())
	s = math.log2(n)
	f = math.floor(s)
	if s - f == 0:
		print(-1)
		continue
	s = -1
	for i in range(f + 1):
		x = 2 ** i
		c = (n + x) // (x * 2)
		s += (c - 1) * x + x
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	answer = -1
	currentVal = 1
	while True:
		if currentVal == n:
			answer = -1
			break
		elif currentVal > n:
			break
		answer += currentVal * ((n + currentVal) // (2 * currentVal))
		currentVal *= 2
	print(answer)


import sys
input = sys.stdin.readline
import math
for _ in range(int(input())):
	N = int(input())
	f = 0
	if 2 ** 30 % N == 0:
		f = 1
	answer = (N - 1) // 2
	p = 2
	total = int(math.log(N, 2))
	for j in range(0, total):
		ans = (N // p - N // (2 * p)) * p
		answer += ans
		p = p * 2
	if f == 1:
		print(-1)
	else:
		print(answer)


from math import log2
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if log2(n) - int(log2(n)) == 0:
		print(-1)
		continue
	m = int(log2(n))
	cost = 0
	cost = cost + int((n + 1) / 2) - 1
	for j in range(1, m + 1):
		p = pow(2, j)
		cost = cost + p * int((n + p) / (2 * p))
	print(cost)


from math import log2
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if log2(n) - int(log2(n)) == 0:
		print('-1')
		continue
	max = int(log2(n))
	ans = 0
	ans += int((n + 1) / 2) - 1
	for i in range(1, max + 1):
		p = pow(2, i)
		ans += p * int((n + p) / (2 * p))
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2 or n & n - 1 == 0:
		print(-1)
		continue
	ans = 0
	ans = ans + n - n // 2
	for i in range(1, math.ceil(math.log2(n)) + 1):
		diff = 1 << i + 1
		first_term = 1 << i
		group_i = (n - first_term) // diff + 1
		ans = ans + group_i * first_term
	print(int(ans - 1))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	if not n & n - 1:
		print(-1)
		continue
	count = (n - 1) // 2
	i = 2
	while i < n:
		count += ((n - i) // (2 * i) + 1) * i
		i <<= 1
	print(count)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	if not n & n - 1:
		print(-1)
	else:
		count = (n - 1) // 2
		i = 1
		while True:
			m = 2 ** i
			if m < n:
				v = (n - m) // (2 * m) + 1
				count += v * m
				i += 1
			else:
				break
		print(count)


import math
for _ in range(int(input())):
	n = int(input())
	cn = n
	bits = int(math.log(n) / math.log(2))
	if 2 ** bits == n:
		print(-1)
	else:
		odd = math.ceil(n / 2) - 1
		sums = 2 ** (bits + 1) - 2
		xsum = 0
		x = 0
		length = int(math.log(n) / math.log(2) + 1)
		index = length - 1
		for i in range(length):
			val = n % 2
			cn = cn >> 1
			if val == 1:
				xsum = xsum + (cn + 1) * 2 ** i
			else:
				xsum = xsum + cn * 2 ** i
			n = n // 2
		print(int(xsum - 1))


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		if N & N - 1 == 0:
			print(-1)
		else:
			counter = (N + 1) // 2 - 1
			nextCost = 2
			while nextCost < N:
				counter += (N - nextCost) // (2 * nextCost) * nextCost + nextCost
				nextCost <<= 1
			print(counter)
main()


for _ in range(int(input())):
	n = int(input())
	if not n & n - 1:
		print(-1)
	else:
		count = (n - 1) // 2
		i = 1
		while True:
			m = 2 ** i
			if m < n:
				v = (n - m) // (2 * m) + 1
				count += v * m
				i += 1
			else:
				break
		print(count)


t = int(input())
answer = ''
for _ in range(t):
	n = int(input())
	if not n & n - 1:
		answer += '-1\n'
		continue
	oddNumCnt = (n + 1) // 2
	cost = oddNumCnt - 1
	currCost = 2
	while currCost < n:
		cost += (n - currCost) // (2 * currCost) * currCost + currCost
		currCost <<= 1
	answer += str(cost) + '\n'
print(answer)


import math

def funn(a, b, n):
	count = a * ((n - a) // (2 * a)) + b
	count = count + a
	return count
t = int(input())
for j in range(t):
	n = int(input())
	if math.log2(n).is_integer():
		print('-1')
	else:
		count = 0
		j = 0
		while 2 ** j < n:
			count = funn(2 ** j, count, n)
			j += 1
		print(count - 1)


def sol(n):
	i = 1
	ans = 0
	while i <= n:
		ans += (n - i) // (i << 1) * i
		i <<= 1
	i = 2
	while i < n:
		ans += i
		i <<= 1
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	if n & n - 1 == 0:
		print(-1)
	else:
		print(sol(n))


for _ in range(int(input())):
	n = int(input())
	answer = 0
	if n % 2 == 0:
		answer += n // 2 - 1
	else:
		answer += n // 2
	x = 2
	while 1:
		if x == n:
			answer = -1
			break
		else:
			q = n // x
			if q == 0:
				break
			if q % 2 == 0:
				answer += x * (q // 2)
			else:
				answer += x * (q // 2 + 1)
		x = x * 2
	print(answer)


from sys import *
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a = bin(n)
	if a.count('1') == 1:
		print(-1)
		continue
	if n == 2:
		print(-1)
		continue
	if n == 3:
		print(3)
		continue
	if n % 2 == 0:
		x = n // 2
	else:
		x = n // 2 + 1
	count = x - 1
	i = 2
	while i <= n:
		l = 0
		k = n // i
		if k % 2 == 0:
			l = k // 2
		else:
			l = k // 2 + 1
		count = count + i * l
		i = i * 2
	print(count)


from math import *
t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	l = log2(n)
	if ceil(l) == floor(l):
		print('-1')
	else:
		sum = -1
		temp = 1
		for i in range(ceil(l)):
			if (n - temp) // (2 * temp) == 0:
				sum = sum + temp
			else:
				sum = sum + (n + temp) // (2 * temp) * temp
			temp = temp * 2
		print(sum)


L = [1 << i for i in range(31)]
for _ in range(int(input())):
	n = int(input())
	t = n
	c = 0
	while t:
		c += 1
		t = t & t - 1
		if c > 1:
			break
	if c == 1:
		print(-1)
		continue
	(res, t, k) = (0, 0, 0)
	while L[t] < n:
		t += 1
	for l in range(t - 1, -1, -1):
		res += L[l] * (int(n / L[l]) - k)
		k = int(n / L[l])
	print(res - 1)


import math
for _ in range(int(input())):
	n = int(input())
	pown = math.log2(n)
	count = -1
	if pown == round(pown):
		print(count)
	else:
		powii = 1
		for i in range(int(pown) + 1):
			powi = powii
			powii = pow(2, i + 1)
			count += powi * (n // powi - n // powii)
		print(count)


import math
t = int(input())
while t:
	n = int(input())
	m = math.log2(n)
	if m == int(m):
		print(-1)
	else:
		m = int(m)
		res = 0
		i = 0
		while n:
			res = res + 2 ** i * math.ceil(n / 2)
			i = i + 1
			n = n // 2
		print(res - 1)
	t = t - 1


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
for _ in range(inp()):
	n = inp()
	if n and (not n & n - 1):
		print(-1)
		continue
	cost = -1
	i = 0
	while n:
		ct = (n - 1) // 2 + 1
		cost += ct * pow(2, i)
		n //= 2
		i += 1
	print(cost)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	pw = 1
	ans = 0
	if n & n - 1 == 0:
		print(-1)
		continue
	while pw <= n:
		ans = ans + (int(n / pw) - int(n / (2 * pw))) * pw
		pw = pw * 2
	print(ans - 1)


l1 = int(input())
for _ in range(l1):
	n = int(input())
	sumi = 0
	if n & n - 1 == 0:
		print(-1)
	else:
		sumi += (n - 1) // 2
		i = 2
		while i <= n:
			temp = n // i
			temp2 = temp + 1
			temp3 = temp2 // 2
			sumi += i * temp3
			i *= 2
		print(sumi)


power = []
val = 1
while val < 1000000000:
	power.append(val)
	val *= 2
power.append(val)
t = int(input())
for T in range(t):
	n = int(input())
	bn = bin(n)[2:]
	if bn.count('1') == 1:
		print(-1)
		continue
	ans = 0
	for i in range(len(power)):
		if power[i] > n:
			break
		ans += power[i] * ((n + power[i]) // (2 * power[i]))
	print(ans - 1)


for _ in range(int(input())):
	n = int(input())
	l = []
	now = 1
	while now < n:
		l.append(now)
		now = now << 1
	l.append(now << 1)
	if now == n:
		print(-1)
		continue
	ans = 0
	for i in range(len(l) - 1):
		ans += l[i] * ((n - l[i]) // l[i + 1])
		ans += l[i] & l[i] + 1
	print(ans)


import math
T = int(input())
for t in range(T):
	n = int(input())
	if n & n - 1 == 0:
		print(-1)
		continue
	sum = 0
	i = 1
	while (n + i) // (i * 2) > 0:
		sum += (n + i) // (i * 2) * i
		i *= 2
	print(sum - 1)


for _ in range(int(input())):
	n = int(input())
	x = 1
	if n & n - 1 == 0:
		print(-1)
	else:
		tot = 0
		while x <= n:
			m = n // x
			t = (m + 1) // 2
			if x > 1:
				c = t * x
			else:
				c = (t - 1) * x
			tot += c
			x <<= 1
		print(tot)


def roads(n):
	res = 0
	if n % 2 == 1:
		res += n // 2
	else:
		res += n // 2 - 1
	i = 2
	while n > 0:
		n //= 2
		if n % 2 == 0:
			res += i * (n // 2)
		else:
			res += i * (n // 2 + 1)
		i <<= 1
	return res
t = int(input())
while t > 0:
	n = int(input())
	(k, c) = (n, 0)
	while k > 0:
		if k & 1 == 1:
			c += 1
		k = k >> 1
	if c == 1:
		print(-1)
	else:
		print(roads(n))
	t -= 1


from math import ceil
from sys import stdin, stdout

def input():
	return stdin.readline()

def main():
	for _ in range(int(input())):
		n = int(input())
		if n & n - 1 == 0:
			print(-1)
			continue
		else:
			i = 0
			ans = 0
			while n > 0:
				d = ceil(n / 2)
				ans += 2 ** i * d
				i = i + 1
				n = n - d
		print(ans - 1)
main()


from math import ceil
for _ in range(int(input())):
	n = int(input())
	if n & n - 1 == 0:
		print(-1)
		continue
	else:
		i = 0
		ans = 0
		while n > 0:
			d = ceil(n / 2)
			ans += 2 ** i * d
			i = i + 1
			n = n // 2
	print(ans - 1)


pow2 = [1]
for i in range(1, 31):
	pow2.append((pow2[-1] << 1) + 1)
pow21 = [1]
for i in range(1, 32):
	pow21.append(pow21[-1] << 1)

def cost(n):
	if n == 0:
		return 0
	idx = 0
	for i in range(31):
		if pow2[i] > n:
			idx = i - 1
			break
	tmp = pow2[idx]
	ans = int((tmp + 1) // 2) * (idx + 1)
	if n > tmp:
		ans += tmp + 1
	ansnew = 0
	if n > tmp:
		ansnew = cost(n - tmp - 1)
	return ans + ansnew
for i in range(int(input())):
	n = int(input())
	if n in pow21:
		print(-1)
	else:
		idx = 0
		for i in range(31):
			if pow2[i] > n:
				idx = i - 1
				break
		tmp = pow2[idx]
		if n == tmp + 1:
			print(cost(n))
		else:
			print(cost(n) - 1)


try:
	n = int(input())
	for i in range(n):
		t = int(input())
		a = 0
		s = 1
		if t & t - 1 == 0:
			print('-1')
			continue
		while s <= t:
			a = a + (int(t / s) - int(t / (s * 2))) * s
			s = s * 2
		print(a - 1)
except:
	pass


import math
arr = []
b = math.log2(10 ** 9) + 1
for i in range(int(b) + 1):
	arr.append(2 ** i)
t = int(input())
for _ in range(t):
	n = int(input())
	a = math.log2(n)
	if int(a) == a:
		print(-1)
	else:
		ans = 0
		for i in range(int(a) + 1):
			ans += (n // arr[i] - n // arr[i + 1]) * arr[i]
		print(ans - 1)


t = int(input())
for xx in range(t):
	n = int(input())
	if n & n - 1 == 0:
		print(-1)
		continue
	res = 0
	if n % 2 == 1:
		res += (n - 1) // 2
		n = res
	else:
		res += n // 2 - 1
		n = n // 2
	i = 2
	while n != 1:
		if n % 2 == 1:
			res += (n + 1) // 2 * i
		else:
			res += n // 2 * i
		n = n // 2
		i = i * 2
	res += i
	print(res)


def isPowerOfTwo(x):
	return x and (not x & x - 1)

def dp(n):
	if isPowerOfTwo(n):
		return -1
	b = bin(n)[2:]
	c = 0
	for i in range(1, len(b)):
		mul = int(b[:i], 2) + 1
		if b[i] == '0':
			mul -= 1
		c += mul * pow(2, len(b) - 1 - i)
	c += pow(2, len(b) - 1)
	return c - 1
t = int(input())
for _ in range(t):
	n = int(input())
	print(dp(n))


for t in range(int(input())):
	n = int(input())
	b_n = bin(n)[2:]
	if b_n.count('1') == 1:
		print(-1)
		continue
	a = n // 2 - (n % 2 == 0)
	q = 2
	while q <= n:
		x = n // q - n // (2 * q)
		a += q * x
		q = q * 2
	print(a)


import sys
input = sys.stdin.readline
import math
for _ in range(int(input())):
	N = int(input())
	odd = math.ceil(N / 2)
	even = N // 2
	f = 0
	if 2 ** 30 % N == 0:
		f = 1
	answer = odd - 1
	i = 2
	while even != 0:
		answer += math.ceil(even / 2) * i
		i = i * 2
		even = even // 2
	if f == 1:
		print(-1)
	else:
		print(answer)


import math as mt
import sys, string
input = sys.stdin.readline
from collections import defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())

def ap(n, a):
	d = a * 2
	terms = (n - a) // d + 1
	return terms * a

def ispower(n):
	s = bin(n)[2:]
	if s.count('1') == 1:
		return True
	return False

def la(n):
	k = 1
	s = 0
	while k < n:
		s += ap(n, k)
		k *= 2
	return s
t = I()
for i in range(t):
	n = I()
	if ispower(n):
		print(-1)
	else:
		print(la(n) - 1)


dp = []
x = 2
while x <= 10 ** 9:
	dp.append(x)
	x = x << 1
for T in range(int(input())):
	n = int(input())
	if n in dp:
		print(-1)
	else:
		res = 0
		for i in range(len(dp)):
			if dp[i] > n:
				break
			num = n // dp[i]
			if num % 2 == 0:
				gr = num // 2
			else:
				gr = (num + 1) // 2
			res += gr * dp[i]
		if n % 2 == 0:
			e = n // 2 - 1
		else:
			e = n // 2
		print(res + e)


import sys
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	if n == 2:
		print(-1)
		continue
	if n == 3:
		print(3)
		continue
	if n % 2 == 0:
		x = n // 2
	else:
		x = n // 2 + 1
	ans = x - 1
	bn = bin(n)
	if bn.count('1') == 1:
		print(-1)
		continue
	p = 2
	while p <= n:
		q = n // p
		if q % 2 == 0:
			l = q // 2
		else:
			l = q // 2 + 1
		ans += l * p
		p *= 2
	print(ans)


from collections import *
from bisect import *
from math import *
from heapq import *
import sys
input = sys.stdin.readline
t = int(input())
pre = [2]
for i in range(30):
	pre.append(pre[-1] * 2)
while t:
	t -= 1
	n = int(input())
	v = bin(n)[2:]
	if v.count('1') == 1:
		print(-1)
		continue
	s = (n + 1) // 2
	s -= 1
	pp = 0
	while pre[pp] <= n:
		s1 = n // pre[pp]
		s2 = n // pre[pp + 1]
		s3 = max(1, s1 - s2)
		if s3 == 1:
			s += int(pre[pp])
		else:
			s += s3 * pre[pp]
		pp += 1
	print(int(s))