For a permutation P of integers from 1 to N, let's define its value as (1 \oplus P_{1}) + (2 \oplus P_{2}) + \ldots + (N \oplus P_{N}). 

Given N, find the maximum possible value of the permutation of integers from 1 to N.

As a reminder, \oplus denotes the bitwise XOR operation

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

The first line of the input contains a single integer T - the number of test cases. The description of test cases follows.

The only line of each test case contains a single integer N.

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

For each test case, output the maximum possible value of the permutation of integers from 1 to N.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$.

------ subtasks ------ 

Subtask 1 (60 points): The sum of $N$ over all test cases doesn't exceed $10^{6}$.
Subtask 2 (40 points): No additional constraints.

----- Sample Input 1 ------ 
5
1
2
3
4
29012022
----- Sample Output 1 ------ 
0
6
6
20
841697449540506
----- explanation 1 ------ 
For $N = 1$, the only such permutation is $P = (1)$, its value is $1 \oplus 1 = 0$. 

For $N = 2$, the permutation with the best value is $P = (2, 1)$, with value $1 \oplus 2 + 2 \oplus 1 = 6$.

For $N = 3$, the permutation with the best value is $P = (2, 1, 3)$, with value $1 \oplus 2 + 2 \oplus 1 + 3 \oplus 3 = 6$.

For $N = 4$, the permutation with the best value is $P = (2, 1, 4, 3)$, with value $1 \oplus 2 + 2 \oplus 1 + 3 \oplus 4 + 4 \oplus 3 = 20$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
def setBitNumber(n):
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n = n + 1
	return n >> 1

def solve(n):
	ans = 0
	while n > 0:
		if n & n + 1 == 0:
			ans += n * (n - 1)
			break
		else:
			k = setBitNumber(n)
			ans += ((k << 2) - 2) * (n - k + 1)
			n = -n + ((k << 1) - 2)
	return ans
for _ in range(int(input())):
	print(solve(int(input())))


t = int(input())
for _ in range(t):
	n = int(input())
	k = n * (n + 1)
	m = 1
	while n > 0:
		if n & 1:
			k -= 2 * m
		else:
			break
		m = m * 2
		n = n >> 1
	print(k)


for i in range(int(input())):
	n = int(input())
	a = n * (n + 1)
	p = 1
	while n > 0:
		if n & 1:
			a -= 2 * p
		else:
			break
		p *= 2
		n = n >> 1
	print(a)


from math import log2
import sys
sys.setrecursionlimit(1000000)

def solve(N):
	if N == 1 or N == 0:
		return 0
	elif N == 2 or N == 3:
		return 6
	elif N == 4:
		return 20
	if log2(N + 1) == int(log2(N + 1)):
		return solve(N - 1)
	pw = 2 ** int(log2(N))
	distance = N - pw + 1
	return 2 * distance * (2 * pw - 1) + solve(N - 2 * distance)
for t in range(int(input())):
	N = int(input())
	print(solve(N))


for i in range(int(input())):
	n = int(input())
	ans = 0
	while n > 1:
		a = bin(n)[2:]
		a = a[::-1]
		b = 0
		p = 1
		for j in a:
			if j == '0':
				b += p
			p *= 2
		if b == 0:
			n -= 1
			continue
		ele = n - b + 1
		ans += ele * (n ^ b)
		n = b - 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [1]
	while l[-1] <= n:
		l.append(l[-1] * 2)
	l.pop()
	ans = n * (n + 1)
	for i in l:
		cnt = n - (i - 1)
		temp = cnt // i
		if temp % 2:
			ext = i
		else:
			ext = cnt % i
		cnt = temp // 2 * i + ext
		if cnt > n - cnt:
			ans = ans - 2 * i
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	final_ans = 0
	while n > 0:
		hpo2 = int(math.log(n, 2))
		ans = 2 ** (hpo2 + 1) - 1
		if n == ans:
			n = n - 1
		else:
			mf = (n - 2 ** hpo2 + 1) * 2
			final_ans = final_ans + ans * mf
			n = n - mf
	print(final_ans)


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	power = []
	for i in range(32):
		power.append((1 << i) - 1)
	ans = 0
	while n > 0:
		if n & n + 1 == 0:
			ans += n * (n - 1)
			break
		else:
			for i in range(1, 32):
				if n > power[i] and n < power[i + 1]:
					ans += 2 * (n - power[i]) * power[i + 1]
					n = -n + 2 * power[i]
					break
	print(ans)


for _ in range(int(input())):

	def check2(n):
		if n and (not n & n - 1):
			return True
		return False

	def next2(n):
		if n and (not n & n - 1):
			return n
		p = 1
		while p < n:
			p <<= 1
		return p

	def ans(x):
		if x == 0:
			return 0
		elif check2(x) and x != 1:
			return x * (x + 1)
		elif check2(x + 1):
			return x * (x - 1)
		else:
			p = next2(x) - 1
			val = x * (x + 1) - (p - x) * (p - x - 1)
			val += ans(p - x - 1)
			return val
	x = int(input())
	print(ans(x))


test = int(input())
for z in range(0, test):
	n = int(input())
	sum = n * (n + 1) // 2
	val = 1
	while n > 0:
		d = n % 2
		n = n // 2
		if d == 0:
			break
		val *= 2
	val -= 1
	sum -= val
	print(sum * 2)


from math import log2

def solver(N):
	ans = 0
	while N > 1:
		hsb = int(log2(N))
		max_value = 2 ** (hsb + 1) - 1
		min_value = max_value ^ N
		if min_value == 0:
			N -= 1
		else:
			ans += max_value * (N - min_value + 1)
			N = min_value - 1
	print(ans)
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	solver(n)


from math import log2

def solver(n):
	ans = 0
	while n > 1:
		hsb = int(log2(n))
		max_value = 0
		for i in range(hsb + 1):
			max_value += 1 << i
		if max_value == n:
			n -= 1
		min_value = max_value ^ n
		ans += max_value * (n - min_value + 1)
		n = min_value - 1
	print(ans)
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	solver(n)


T = int(input())
for i in range(T):
	n = int(input())
	hsd = 31
	maxsum = 0
	while n > 1:
		while hsd >= 0 and 1 << hsd & n == 0:
			hsd -= 1
		maxval = 0
		for i in range(hsd + 1):
			maxval += 1 << i
		if maxval == n:
			n = n - 1
			continue
		lstval = maxval - n
		maxsum += maxval * (n - lstval + 1)
		n = lstval - 1
	print(maxsum)


import math
t = int(input())

def f(n):
	var = int(math.log(n, 2))
	xorv = 2 ** (var + 1) - 1
	return xorv
while t:
	s = 0
	n = int(input())
	if n == 1:
		print(0)
		t -= 1
		continue
	elif n & n - 1 == 0:
		print(n * (n + 1))
		t -= 1
		continue
	elif n & n + 1 == 0:
		print(n * (n - 1))
		t -= 1
		continue
	i = n
	while i > 1:
		if i & i + 1 == 0:
			i -= 1
		pv = i
		i = (i ^ f(i)) - 1
		s += (pv - i) * f(pv)
	print(s)
	t -= 1


import bisect

def fun(n):
	if n == 0 or n == -1 or n == 1:
		return 0
	k = 2 ** bisect.bisect_left(a, n) - n - 2
	if k == -1:
		return fun(n - 1)
	if k < 0:
		k = 0
	return (n + k + 1) * (n - k) + fun(k)
a = []
i = 0
n = 1
while n < 1000000000:
	a.append(n)
	n = n * 2
for t in range(int(input())):
	i = int(input())
	print(fun(i))


case = int(input())
l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824]
for r in range(case):
	n = int(input())
	if n == 1:
		print(0)
		continue
	count = 0
	i = 0
	while n >= l[i]:
		i += 1
	i -= 1
	while n > 0:
		if n == l[i + 1] - 1:
			n -= 1
		count += (n - l[i] + 1) * 2 * (l[i + 1] - 1)
		n = n - (n - l[i] + 1) * 2
		while n >= l[i]:
			i += 1
		i -= 1
	print(count)


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
		continue
	s = 0
	t = 1
	while t <= n:
		t = t * 2
	if n + 1 == t:
		print((n - 1) * (t - 1))
		continue
	t = t // 2
	while n > 1:
		s += (2 * t - 1) * 2 * (n - t + 1)
		n = t - (n - t + 1) - 1
		t = 1
		while t <= n:
			t = t * 2
		if n + 1 == t:
			s += (n - 1) * (t - 1)
			n = 0
		t = t // 2
	print(s)


for i in range(int(input())):
	n = int(input())
	ans = 0
	while 1:
		if n <= 1:
			break
		l = len(bin(n)[2:])
		hp2 = 2 ** l - 1
		rem = n % 2 ** (l - 1)
		n = n - (rem + 1) * 2
		if n < 0:
			rem -= 1
		ans += (rem + 1) * 2 * hp2
	print(ans)


import math
for i in range(int(input())):
	x = int(input())

	def Log2(x):
		if x == 0:
			return false
		return math.log10(x) / math.log10(2)

	def isPowerOfTwo(n):
		return math.ceil(Log2(n)) == math.floor(Log2(n))

	def nextPowerOf2(n):
		p = 1
		if n and (not n & n - 1):
			return n
		while p < n:
			p <<= 1
		return p

	def pow(x):
		if x == 0:
			return 0
		if isPowerOfTwo(x) == True and x != 1:
			return x * (x + 1)
		elif isPowerOfTwo(x + 1) == True:
			return x * (x - 1)
		else:
			pz = nextPowerOf2(x) - 1
			ans = x * (x + 1) - (pz - x - 1) * (pz - x)
			ans += pow(pz - x - 1)
			return ans
	print(pow(x))


li = [2 ** x for x in range(31)]
T = int(input())
for i in range(T):
	n = int(input())
	val = 0
	x = 30
	while x >= 0 and n > 1:
		if li[x] - 1 == n:
			n -= 1
		if li[x] <= n:
			t = (n - li[x] + 1) * 2
			val = val + (2 * li[x] - 1) * t
			n = n - t
		x -= 1
	print(val)


y = int(input())
for _ in range(y):
	N = int(input())
	s = 0
	i = N
	d = {}
	while i > 0:
		bit = format(i, 'b')
		l = len(bit)
		for j in range(l):
			if bit[j] == '0':
				c = ['1' for x in range(l)]
				break
		else:
			c = ['1' for x in range(l + 1)]
		c = ''.join(c)
		p = int(c, 2)
		t = i ^ p
		if t > N:
			i -= 1
			continue
		if t in d:
			i -= 1
			continue
		else:
			d[t] = 1
		s += (i - t + 1) * p
		i = t - 1
	print(s)


def xorsum(n):
	(num, count) = (0, 0)
	while n > 0:
		if n % 2 == 0:
			num += 1 << count
		n //= 2
		count += 1
	return num
for _ in range(int(input())):
	n = int(input())
	ans = 0
	while n > 0:
		a = xorsum(n)
		b = n
		if b & b + 1 == 0:
			b -= 1
		v = b * (b + 1) // 2 - a * (a - 1) // 2
		ans += v * 2
		n = a - 1
	print(int(ans))


tests = int(input())
for t in range(tests):
	n = int(input())
	m = n + 1 & -n - 1
	print(n * (n + 1) - 2 * (m - 1))


T = int(input())
power_2 = []
cur = 2
while cur < 2 * 10 ** 9:
	power_2.append(cur)
	cur *= 2
for i in range(T):
	N = int(input())
	answer = 0
	pnt = 0
	while N >= power_2[pnt]:
		pnt += 1
	while pnt > 0:
		if (power_2[pnt] - 1) // 2 > N:
			pnt -= 1
			continue
		pair = N - power_2[pnt - 1] + 1
		if N == power_2[pnt] - 1:
			pair -= 1
		answer += (power_2[pnt] - 1) * pair * 2
		N = power_2[pnt] - 1 - N - 1
		pnt -= 1
	print(answer)


from math import log2, ceil
t = int(input())
for _ in range(t):
	n = int(input())
	mx = 2 ** (int(log2(n)) + 1) - 1
	if mx - n <= 1:
		print(mx * (mx - 1))
	else:
		ans = 0
		while n > 1:
			mx = 2 ** (int(log2(n)) + 1) - 1
			mul = min(n - (mx - n) + 1, n if n % 2 == 0 else n - 1)
			ans += mx * mul
			n = mx - n - 1
		print(ans)


def inversion(nu):
	nus = str(bin(nu))[2:]
	st = ''
	for x in nus:
		if x == '0':
			st += '1'
		else:
			st += '0'
	return int(st, 2)
for tc in range(int(input())):
	n = int(input())
	res = 0
	num = n
	while num > 0:
		inv = inversion(num)
		if 1 <= inv <= n:
			req = (num - inv + 1) * (num ^ inv)
			res += req
			num = inv - 1
		else:
			num -= 1
	print(res)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		if n % 2 == 0:
			print(n ** 2 + n)
		elif n % 4 == 3:
			b = bin(n).replace('0b', '')
			b = list(b)
			res = 0
			while b and b[-1] == '1':
				b.pop()
				res += 1
			print(n ** 2 + n - int('1' * res, 2) * 2)
		else:
			print(n ** 2 + n - 2)
main()


from collections import defaultdict, deque
from typing import Counter
import math
import sys
from string import ascii_lowercase

def readInt():
	x = int(sys.stdin.readline().rstrip())
	return x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x
write = sys.stdout.write
read = sys.stdin.readline

def getcount(n, k):
	res = n >> k + 1 << k
	if n >> k & 1:
		res += n & (1 << k) - 1
	return res

def solve():
	n = readInt()
	ans = 0
	for i in range(30):
		k = getcount(n + 1, i)
		ans += min(k, n - k) * (1 << i)
	print(ans * 2)

def main():
	t = 1
	t = readInt()
	for _ in range(t):
		solve()
main()


def get_pw_bot(x):
	sum = 1
	while sum <= x:
		sum *= 2
	sum //= 2
	return sum

def solve():
	n = int(input())
	ans = 0
	while n > 0:
		if n & n + 1 == 0:
			n -= 1
			continue
		bot_pw = get_pw_bot(n)
		cnt = n - bot_pw + 1
		val = bot_pw * 2 - 1
		ans += 2 * cnt * val
		n -= 2 * cnt
	print(ans)
tst = int(input())
for tt in range(tst):
	solve()


def solve(num, tmp=0, tot=0):
	while num != 0:
		if num % 2 == 0:
			tmp += 1 << tot
		num //= 2
		tot += 1
		if num <= 0:
			break
	return tmp
for tcs in range(int(input())):
	num = int(input())
	res = 0
	while num > 0:
		a = solve(num)
		b = num
		if b & b + 1 == 0:
			b -= 1
		num = (b * (b + 1) >> 1) - (a * (a - 1) >> 1)
		res += num << 1
		num = a - 1
	print(res)


from collections import defaultdict
t = int(input())
vals = defaultdict(lambda : -1)

def solve(n):
	if n <= 1:
		return 0
	if vals[n] != -1:
		return vals[n]
	a = bin(n)[2:]
	b = ''
	for x in a:
		if x == '1':
			b += '0'
		else:
			b += '1'
	a = int(a, 2)
	b = int(b, 2)
	if b == 0:
		b = 1
		a -= 1
	vals[n] = (a ^ b) * (a - b + 1) + solve(b - 1)
	return vals[n]
while t > 0:
	n = int(input())
	print(solve(n))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	pre = n * (n + 1)
	i = 1
	while n:
		if n % 2:
			pre -= 1 << i
		else:
			break
		n //= 2
		i += 1
	print(pre)


from math import log
T = int(input())
for _ in range(T):
	N = int(input())
	P1 = []
	ans = 0
	i = N
	while i > 0:
		x = 2 ** (int(log(i, 2)) + 1) - 1
		if x == i:
			i -= 1
		else:
			ans += x * (2 * i - x + 1)
			i = x - i - 1
			continue
	print(ans)


import math
import bisect
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter
INF = 10 ** 20
mod = 1000000007

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def process(N):
	if not N % 2:
		return N * (N + 1)
	else:
		ans = N * (N + 1)
		temp = N ^ N + 1
		return ans - (temp ^ 1)

def main():
	for _ in range(int(input())):
		N = int(input())
		print(process(N))
main()


test_cases = int(input())

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n

def dum(n, sums):
	if n == 0:
		return sums
	elif n == 1:
		return sums
	elif n == 2:
		sums += 6
		return sums
	val = nextPowerOf2(n)
	if val - n >= 2:
		sums += (val - 1) * (val - 2 - (val - 2 - n) * 2)
	else:
		if val - n == 0:
			sums += (val + val - 1) * 2
		elif val - n == 1:
			sums += 0
		n = val - 2
		sums += (val - 1) * (val - 2 - (val - 2 - n) * 2)
	p1 = val - 2 - n
	return dum(p1, sums)
for lol in range(test_cases):
	sums = 0
	n = int(input())
	print(dum(n, sums))


from math import log2

def solve(num):
	if num == 1:
		return 0
	if num == 2:
		return 6
	if num == 3:
		return 6
	finalAnswer = 0
	numBin = bin(num)[2:]
	negBin = ''
	finalSum = 0
	for i in numBin:
		finalSum += 1
		if i == '1':
			negBin += '0'
		else:
			negBin += '1'
	finalSum = 2 ** (finalSum - 1) - 1
	numNegBin = int(negBin, 2)
	if numNegBin == 0:
		finalAnswer = -2 * num
	if numNegBin > 1:
		finalAnswer += solve(numNegBin - 1)
	xor = num ^ numNegBin
	finalAnswer += 2 * (num - finalSum) * xor
	return finalAnswer
	pass
for _ in range(int(input())):
	num = int(input())
	print(solve(num))


from sys import stdin
from collections import defaultdict as dd, deque as dq
from heapq import heappush as hpush, heappop as hpop
from bisect import bisect_left as bl, bisect_right as br
from random import randint
from math import sqrt, ceil, floor, log2

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def text():
	return stdin.readline().rstrip()

def num():
	return int(text())

def mp(dt):
	return map(dt, stdin.readline().split())

def array(dt):
	return list(mp(dt))

def flipp(num):
	x = int(log2(num)) + 1
	for i in range(x):
		num = num ^ 1 << i
	return num
t = num()
while t > 0:
	n = num()
	ans = 0
	while n >= 1:
		flipper = flipp(n)
		curr = n
		if curr & curr + 1 == 0:
			curr -= 1
		ans += 2 * (curr * (curr + 1) // 2 - flipper * (flipper - 1) // 2)
		n = flipper - 1
	print(ans)
	t -= 1


def find(n):
	no = 0
	c = 0
	while n > 0:
		if n % 2 == 0:
			no = no + (1 << c)
		n = n // 2
		c = c + 1
		if n <= 0:
			break
	return no
t = int(input())
for _ in range(t):
	num = int(input())
	res = 0
	while num > 0:
		x = find(num)
		y = num
		if y & y + 1 == 0:
			y = y - 1
		temp = y * (y + 1) // 2 - x * (x - 1) // 2
		res = res + temp + temp
		num = x - 1
	print(res)


pow2 = [1]
for i in range(31):
	pow2.append(2 * pow2[-1])
for i in range(len(pow2)):
	pow2[i] -= 1
N = len(pow2)

def AbhiSolveKiya(n):
	if n == 1:
		return 0
	ans = 0
	while n > 0:
		j = 0
		while j < N and n > pow2[j]:
			j += 1
		p = pow2[j]
		xorr = p ^ n
		if xorr == 0:
			n -= 1
		else:
			ans += p * (n - xorr + 1)
			n = xorr - 1
	return ans
for _ in range(int(input())):
	n = int(input())
	print(AbhiSolveKiya(n))


def solve(n):
	(t, c) = (0, 0)
	while n:
		if n % 2 == 0:
			t += 1 << c
		n = n // 2
		c += 1
		if n < 0:
			break
	return t
for _ in range(int(input())):
	n = int(input())
	ans = 0
	while n > 0:
		t = solve(n)
		temp = n
		if temp & temp + 1 == 0:
			temp -= 1
		val = temp * (temp + 1) // 2 - t * (t - 1) // 2
		ans += val * 2
		n = t - 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	power = 1
	total = 0
	while n > 1:
		if power * 2 <= n:
			power *= 2
			continue
		if n == power * 2 - 1:
			total += (power - 1) * 2 * (power * 2 - 1)
			break
		total += (n - (power - 1)) * 2 * (power * 2 - 1)
		n = power - (n - (power - 2))
		power = 1
	print(total)


import math

def solve(i):
	if i == 1:
		print(0)
		return
	curr = i
	summ = 0
	val = int(math.log2(curr)) + 1
	while val > 0:
		val = int(math.log2(curr)) + 1
		s = 2 ** val - 1
		t = s - curr
		if t == 0:
			curr -= 1
			if curr <= 1:
				break
			continue
		summ += (curr - t + 1) // 2 * 2 * s
		curr = t - 1
		if curr <= 1:
			break
	print(int(summ))
t = int(input())
for i in range(t):
	v = int(input())
	solve(v)


def invert(N):
	num = shift = 0
	while N:
		if N ^ 1 == N + 1:
			num += 1 << shift
		N = N // 2
		shift += 1
		if N <= 0:
			break
	return num
for _ in range(int(input())):
	N = int(input())
	ans = 0
	while N > 0:
		new = invert(N)
		curr = N
		if new & curr + 1 == 0:
			curr -= 1
		cal = curr * (curr + 1) // 2 - new * (new - 1) // 2
		ans += cal * 2
		N = new - 1
	print(ans)


def func(N):
	n = 0
	cnt = 0
	while N:
		if N % 2 == 0:
			n += 1 << cnt
		N = N // 2
		cnt += 1
		if N <= 0:
			break
	return n
for _ in range(int(input())):
	N = int(input())
	ans = 0
	while N > 0:
		a = func(N)
		b = N
		if b & b + 1 == 0:
			b -= 1
		val = b * (b + 1) // 2 - a * (a - 1) // 2
		ans += val * 2
		N = a - 1
	print(ans)


def h(n):
	no = 0
	cnt = 0
	while n:
		if n % 2 == 0:
			no += 1 << cnt
		n //= 2
		cnt += 1
		if n <= 0:
			break
	return no
t = int(input())
while t:
	n = int(input())
	ans = 0
	while n > 0:
		a = h(n)
		b = n
		if b & b + 1 == 0:
			b -= 1
		val = b * (b + 1) // 2 - a * (a - 1) // 2
		ans += val * 2
		n = a - 1
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	ans = 0

	def met1(x):
		(a, c) = (0, 0)
		while x:
			if x % 2 == 0:
				a += 1 << c
			x = x // 2
			c += 1
			if x <= 0:
				break
		return a
	while n > 0:
		b = met1(n)
		c = n
		if c & c + 1 == 0:
			c = c - 1
		val = c * (c + 1) // 2 - b * (b - 1) // 2
		ans += val * 2
		n = b - 1
	print(ans)


from collections import defaultdict
import math

def ok(n):
	(num, count) = (0, 0)
	while n > 0:
		if n % 2 == 0:
			num += 1 << count
		n = n // 2
		count += 1
	return num
for _ in range(int(input())):
	n = int(input())
	ans = 0
	while n > 0:
		a = ok(n)
		b = n
		if b & b + 1 == 0:
			b -= 1
		c = b * (b + 1) // 2 - a * (a - 1) // 2
		ans += c * 2
		n = a - 1
	print(ans)


import sys
input = lambda : sys.stdin.readline().strip()
t = int(input())
while t:
	t -= 1
	n = int(input())
	if n % 4 == 0 or n % 4 == 2:
		print(n * (n + 1))
	elif n % 4 == 1:
		print(n * (n + 1) - 2)
	else:
		N = list(bin(n)[2:])
		res = 0
		while N and N[-1] == '1':
			N.pop()
			res += 1
		print(n * (n + 1) - int('1' * res, 2) * 2)


def func(n):
	a = 0
	cnt = 0
	while n:
		if not n % 2:
			a += 1 << cnt
		n //= 2
		cnt += 1
		if n <= 0:
			break
	return a
for _ in range(int(input())):
	n = int(input())
	ans = 0
	while n > 0:
		x = func(n)
		y = n
		if not y & y + 1:
			y -= 1
		v = y * (y + 1) // 2 - x * (x - 1) // 2
		ans += v * 2
		n = x - 1
	print(ans)


def conj(n):
	o = n
	x = 0
	while n > 0:
		x += 1
		n >>= 1
	m = (1 << x) - 1
	return o ^ m

def func(n):
	if n <= 1:
		return 0
	c = conj(n)
	if c == 0:
		return func(n - 1)
	return (n + c) * (n - c + 1) + func(c - 1)
for t in range(int(input())):
	n = int(input())
	print(func(n))


import math
for _ in range(int(input())):
	n = int(input())
	ans = 0
	while n > 1:
		a = int(math.log(n, 2)) + 1
		v = 2 ** a - 1
		num = n - (2 ** (a - 1) - 1)
		gp = min(num, n // 2)
		ans += gp * 2 * v
		n -= 2 * gp
	print(ans)


def hs(n):
	q = 0
	p = 0
	while n:
		if n % 2 == 0:
			q += 1 << p
		n = n // 2
		p += 1
		if n <= 0:
			break
	return q
for _ in range(int(input())):
	n = int(input())
	ans = 0
	while n > 0:
		a = hs(n)
		b = n
		if b & b + 1 == 0:
			b -= 1
		v = b * (b + 1) // 2 - a * (a - 1) // 2
		ans += v * 2
		n = a - 1
	print(ans)


def func(n):
	c = 0
	pow = 1
	while n != 0:
		c += pow
		pow *= 2
		n = n >> 1
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	while n > 0:
		x = func(n)
		if x - n == 0:
			n -= 1
			continue
		diff = n - (x - n) + 1
		ans += x * diff
		n = x - n - 1
	print(ans)


from sys import stdin, stdout, maxsize
from math import sqrt, log, factorial as ft, gcd, ceil, floor
from collections import defaultdict
ii = lambda : int(input())
di = lambda : defaultdict(lambda : 0)
dl = lambda : defaultdict(lambda : list())
li = lambda : list(map(int, stdin.readline().strip().split()))
mi = lambda : map(int, stdin.readline().strip().split())
si = lambda : stdin.readline().strip()
p = 2
l1 = []
l2 = [0]
for i in range(35):
	l1.append(p - 1)
	l2.append(p)
	p += p
l2.pop()
for _ in range(ii()):
	n = ii()
	ans = 0
	while n > 1:
		ix = 0
		for i in range(34, -1, -1):
			if l2[i] <= n:
				ix = i
				break
		diff = n - l2[ix] + 1
		if 2 * diff > n:
			diff -= 1
		ans += 2 * diff * l1[ix]
		n -= 2 * diff
	print(ans)


t = int(input())
for d in range(t):
	n = int(input())
	num = 0
	maxi = 2147483647
	i = 1
	while i < maxi:
		if i > n:
			num = i
			break
		i *= 2
	ans = 0
	while n > 1:
		if n == num - 1:
			n -= 1
		mx = num - 1
		start = mx ^ n
		ans += mx * (n - start + 1)
		n = start - 1
		i = 1
		while i < maxi:
			if i > n:
				num = i
				break
			i *= 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	power = 1
	for i in range(32):
		arr.append(power)
		power *= 2

	def low(n, arr):
		for i in range(32):
			if arr[i] > n:
				return i
		return -1

	def recurse(n):
		if n <= 1:
			return 0
		power = low(n, arr)
		power -= 1
		rem = 2 ** power - 1
		more = n - rem
		if more > rem:
			more = rem
		rem -= more
		summ = 2 * more * (2 ** (power + 1) - 1)
		return summ + recurse(rem)
	print(recurse(n))


def next_2(n):
	if n < 2:
		return 0
	x = 1
	while n // x != 0:
		x *= 2
	return x

def fn(n):
	power = next_2(n)
	if power == 0:
		return 0
	multiplier = power - 1
	if n == multiplier:
		return multiplier * (multiplier - 1)
	remainder = multiplier - 1 - n
	points = n - remainder
	return multiplier * points + fn(remainder)
for _ in range(int(input())):
	n = int(input())
	print(fn(n))


def f(n):
	i = 1
	while 2 * i <= n:
		i = 2 * i
	return i
T = int(input())
for _ in range(T):
	n = int(input())
	ans = 0
	while n > 1:
		x = f(n)
		if x == n:
			ans += (2 * x - 1) * 2 + (x - 1) * (n - 2)
			n = 0
			continue
		ans += min(x - 1, n - x + 1) * 2 * (x * 2 - 1)
		n -= min(x - 1, n - x + 1) * 2
	print(ans)


def solve(n):
	c = 0
	while n > 0:
		a = bin(n)
		a = a[2:]
		s = ''
		for i in a:
			if i == '1':
				s = s + '0'
			else:
				s = s + '1'
		s = int(s, 2)
		if s > 0:
			k = n - s + 1
			c = c + k * (n ^ s)
			n = s - 1
		else:
			n = n - 1
	print(c)
t = int(input())
for test in range(t):
	num = int(input())
	solve(num)


def sol():
	n = int(input())
	c = 0
	while n > 0:
		a = bin(n)
		a = a[2:]
		s = ''
		for i in a:
			if i == '1':
				s = s + '0'
			else:
				s = s + '1'
		s = int(s, 2)
		if s > 0:
			k = n - s + 1
			c = c + k * (n ^ s)
			n = s - 1
		else:
			n = n - 1
	print(c)
t = int(input())
for x in range(t):
	sol()


import math

def setBitNumber(n):
	return 1 << int(math.log2(n))
for _ in range(int(input())):
	n = int(input())
	temp = 0
	while n > 0:
		c = n + 1
		if c & c - 1 == 0:
			n -= 1
		if n == 0:
			break
		x = setBitNumber(n)
		a = n - x + 1
		temp += a * 2 * (x ^ x - 1)
		n -= 2 * a
	print(temp)


meme = {1: 0}

def cal(n):
	if n in meme:
		return meme[n]
	nn = n
	count = 0
	while n > 0:
		count += 1
		n = n // 2
	if nn == 2 ** (count - 1):
		res = nn * (nn + 1)
	elif nn == 2 ** count - 1 or nn == 2 ** count - 2:
		res = (2 ** count - 1) * (2 ** count - 2)
	else:
		rmd = 2 ** count - 1 - nn
		m = nn - rmd + 1
		res = m * (2 ** count - 1) + cal(rmd - 1)
	meme[nn] = res
	return res
t = int(input())
for ti in range(t):
	n = int(input())
	print(cal(n))


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	ans = 0
	while n > 1:
		k = 1
		while k * 2 <= n:
			k *= 2
		if k == n:
			ans += (2 * k - 1) * 2 + (k - 1) * (n - 2)
			n = 0
			continue
		ans += min(k - 1, n - k + 1) * 2 * (k * 2 - 1)
		n -= min(k - 1, n - k + 1) * 2
	print(ans)


from math import log2, ceil, floor
t = int(input())

def solve(N):
	if N <= 1:
		return 0
	if log2(N + 1) % 1 == 0:
		N -= 1
	if log2(N) % 1 == 0:
		return (N * 2 - 1) * 2 + (N - 1) * (N - 2)
	np2 = 2 ** ceil(log2(N)) - 1
	lp2 = 2 ** floor(log2(N))
	n = N - lp2 + 1
	ans = n * np2 * 2
	return solve(N - n * 2) + ans
	return ans
while t:
	N = int(input())
	print(solve(N))
	t -= 1


arr = []
po = 1
for i in range(32):
	arr.append(po)
	po *= 2

def less(n, arr):
	for i in range(32):
		if arr[i] > n:
			return i
	return -1

def recur(n):
	if n <= 1:
		return 0
	po = less(n, arr)
	po -= 1
	rem = 2 ** po - 1
	extra = n - rem
	if extra > rem:
		extra = rem
	rem -= extra
	su = 2 * extra * (2 ** (po + 1) - 1)
	return su + recur(rem)
try:
	for tc in range(int(input())):
		n = int(input())
		print(recur(n))
except:
	pass


import sys

def rall():
	return sys.stdin.readlines()

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

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())

def next_pow2(n):
	t = 1
	while t < n:
		t *= 2
	return t

def solve(i):
	small = [0, 0, 6, 6, 20]
	if i <= 4:
		return small[i]
	allones = next_pow2(i) - 1
	if i == allones:
		return solve(i - 1)
	elif i == allones + 1:
		allones = (allones + 1) * 2 - 1
	opp = allones - i
	return allones * (i - opp + 1) + solve(opp - 1)
for ti in range(NT):
	n = int(rl())
	pr(solve(n))


from sys import stdin
import math

def solve(n):
	if n == 0:
		return 0
	b = bin(n).replace('0b', '')
	x = len(b)
	if b.count('1') == x:
		return (n - 1) * n
	y = int('1' * x, 2)
	n = y - n - 1
	return 2 * (y // 2 - n) * y + solve(n)
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	print(solve(n))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	while n > 0:
		a = math.floor(math.log(n, 2))
		num = 2 ** a
		b = n - num + 1
		ans = ans + 2 * b * (2 * num - 1)
		if n == 2 * num - 1:
			ans = ans - 2 * (2 * num - 1)
		n = n - 2 * b
	print(ans)


from math import log
for _ in range(int(input())):
	n = int(input())

	def solve(n):
		if n <= 1:
			return 0
		p = int(log(n, 2)) + 1
		val = 2 ** p - 1
		number = n - (2 ** (p - 1) - 1)
		grp = min(number, n // 2)
		ans = grp * 2 * val
		n -= 2 * grp
		ans += solve(n)
		return ans
	print(solve(n))


for some_random_name in range(int(input())):
	n = int(input())
	p = 1
	a = []
	while p <= n:
		x = (n + 1) // p
		if x % 2 == 0:
			ans = x // 2 * p
		else:
			ans = x // 2 * p + (n + 1) % p
		a.append(ans)
		p *= 2
	ans = 0
	for i in range(len(a)):
		ans += 2 ** i * min(a[i], n - a[i]) * 2
	print(ans)


def f(N):
	max_deg = 0
	M = N + 1
	while M % 2 == 0:
		M = M // 2
		max_deg += 1
	return max_deg
T = int(input())
for _ in range(T):
	N = int(input())
	s = f(N)
	answer = N * (N + 1) - 2 ** (s + 1) + 2
	print(answer)


def invert(s):
	com = bin(s)[2:]
	bs = ''
	for i in com:
		if i == '1':
			bs += '0'
		else:
			bs += '1'
	return int(bs, 2)

def solve(n: int):
	n2 = n
	sum = 0
	while n2 > 0:
		inv_n2 = invert(n2)
		if inv_n2 == 0:
			sum += n2 * (n2 - 1)
		else:
			sum += (inv_n2 + n2) * (n2 - inv_n2 + 1)
		n2 = inv_n2 - 1
	print(sum)
for testcase in range(int(input())):
	n = int(input())
	solve(n)


def case(N):
	n = N
	sum = 0
	while n > 0:
		bit = n.bit_length() - 1
		pow = 2 ** bit - 1
		d = n - pow
		n = n - d * 2
		sum += ((pow << 1) + 1) * min(d, pow)
	return sum * 2
for _ in range(int(input())):
	print(case(int(input())))


import sys
input = sys.stdin.readline

def DFS(x):
	if x == 0:
		return 0
	b = bin(x)[2:]
	if '0' not in b:
		return DFS(x - 1)
	full_mask = int('1' * len(b), 2)
	compliment = full_mask ^ x
	return (x - compliment + 1) * full_mask + DFS(compliment - 1)
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	print(DFS(n))


from itertools import permutations

def solve(x):
	if x <= 1:
		return 0
	if x & x + 1 == 0:
		return solve(x - 1)
	pow2 = 1 << len(bin(x)) - 2
	smallest = pow2 - x - 1
	res = (x - smallest + 1) * (pow2 - 1) + solve(smallest - 1)
	return res
T = int(input())
for _ in range(T):
	n = int(input())
	if n & n + 1 == 0:
		print(solve(n - 1))
	else:
		print(solve(n))


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
sys.setrecursionlimit(10 ** 8)
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353

def get(n):
	if n <= 0:
		return 0
	b = len(bin(n)[2:])
	if 2 ** b - 1 == n:
		n -= 1
	le = n - pow(2, b - 1) + 1
	ans = get(pow(2, b - 1) - le - 1)
	ans += le * (pow(2, b) - 1)
	return ans
for _ in range(ii()):
	n = ii()
	if n == 1:
		print(0)
		continue
	tot = get(n)
	print(tot * 2)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def flip(a, l, r):
	for i in range(l, r):
		a[i] = '0' if a[i] == '1' else '1'
	return

def get_ans(n):
	if n <= 0:
		return 0
	c = len(bin(n)[2:])
	if pow(2, c) - 1 == n:
		n -= 1
	left = n - pow(2, c - 1) + 1
	ans = get_ans(pow(2, c - 1) - left - 1)
	ans += left * (pow(2, c) - 1) * 2
	return ans

def hnbhai(tc):
	n = sb()
	if n == 1:
		print(0)
		return
	print(get_ans(n))
for _ in range(sb()):
	hnbhai(_ + 1)


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
tc = 1
tc = int(input())
for test_cases in range(1, tc + 1):
	n = int(input())

	def solve(n):
		if n < 2:
			return 0
		t = len(bin(n)) - 2
		if 1 << t == n + 1:
			n -= 1
		a = (1 << t) - 1 - n - 1
		b = (1 << t) - 2 * a - 2
		return b * ((1 << t) - 1) + solve(a)
	ans = solve(n)
	print(ans)