In this problem you are to calculate the sum of all integers from 1 to n, but you should take all powers of two with minus in the sum.

For example, for n = 4 the sum is equal to  - 1 - 2 + 3 - 4 =  - 4, because 1, 2 and 4 are 2^0, 2^1 and 2^2 respectively.

Calculate the answer for t values of n.


-----Input-----

The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of values of n to be processed.

Each of next t lines contains a single integer n (1 ≤ n ≤ 10^9).


-----Output-----

Print the requested sum for each of t integers n given in the input.


-----Examples-----
Input
2
4
1000000000

Output
-4
499999998352516354



-----Note-----

The answer for the first sample is explained in the statement.

Difficulty: interview

Starter code:

Solutions:
from math import floor,log
for _ in range(int(input())):
    n=int(input())
    p=(n*(n+1))//2
    f=floor(log(n,2))
    p-=2*(2**(f+1)-1)
    print(p)


T = int(input())
for cas in range(T):
    n = int(input())
    res = n * (n + 1) // 2
    for i in range(40):
        if (1<<i) > n:
            break
        else:
            res -= 2 * (1<<i)
    print (res)

def solve(n):
    r = n*(n+1)//2
    i = 1
    while i <= n:
        r -= i * 2
        i *= 2
    return r

t = int(input())
for i in range(t):
    print(solve(int(input())))


t = int(input())
for test in range(t):
    n = int(input())
    a = 1
    cnt = 0
    while a <= n:
        a *= 2
        cnt += 1
    print(n*(n + 1)//2 - 2 * (2**cnt - 1))
    
        
    


for _ in range(int(input())):
    N = int(input())
    ans = N * (N + 1) // 2
    i = 1
    while i <= N:
        ans -= 2 * i
        i <<= 1
    print(ans)


import math
from decimal import *
import sys
from fractions import Fraction

T=int(input())

for j in range(0,T):

    n = int(input())

    t = 1
    lt = 0
    while 2*t <= n:
        t*=2
        lt+=1


    n2 = Fraction(n*(n+1))/Fraction(2)
    print(n2 - 2*(2*t-1))


    
    


def sum_n(n):
    return n*(n+1)//2
def main():
    mode="filee"
    if mode=="file":f=open("test.txt","r")
    get = lambda :[int(x) for x in (f.readline() if mode=="file" else input()).split()]
    [t]=get()
    for z in range(t):
        [n]=get()
        hold = sum_n(n)
        j = 1
        while j<=n:
            j = j<<1
            hold-=j
        print(hold)
    


    if mode=="file":f.close()


def __starting_point():
    main()

__starting_point()

t = int(input())
for i in range(t):
    n = int(input())
    sum = n * (n + 1) // 2
    j = 0
    while 2 ** j <= n:
        sum -= (2 ** j) * 2
        j += 1
    print(sum)


t = int(input())
for i in range(t):
	n = int(input())
	n1 = n
	q = 1
	while n1 != 0:
		n1 = n1 // 2
		q *= 2
	q = q // 2
	print(n * (n + 1) // 2 - 2 * (2 * q - 1))

import math

def cal(val):
    k = int(math.log2(val))
    return (1 + val) * val // 2 - 2 * (2 ** (k + 1) - 1)

N = int(input())
for i in range(N):
    print(cal(int(input())))

for t in range(int(input())):
    n = int(input())
    v, p2 = n * (n + 1) // 2, 1
    while p2 <= n:
        v -= 2 * p2
        p2 *= 2
    print(v)

"""
Codeforces Educational Round

Problem 598 A Tricky Sum

@author yamaton
@date 2015-11-12
"""

import itertools as it
import functools
import operator
import collections
import math
import sys


def solve(x):
    simple_sum = x * (x + 1) // 2

    pow = -1
    while x > 0:
        x >>= 1
        pow += 1

    sum_power_of_twos = 2**(pow + 1) - 1
    return simple_sum - 2 * sum_power_of_twos


def p(*args, **kwargs):
    return print(*args, file=sys.stderr, **kwargs)

def main():
    t = int(input())
    xs = [int(input()) for _ in range(t)]

    results = [solve(x) for x in xs]
    for res in results:
        print(res)


def __starting_point():
    main()

__starting_point()

# import sys
# sys.stdin = open('cf598a.in')

def smaller_power(n):
	cpow = -1
	while n:
		n >>= 1
		cpow += 1
	return 1 << cpow

t = int(input())

for _ in range(t):
	n = int(input())
	sum_full = n * (n + 1) // 2
	sum_powers = (smaller_power(n) << 1) - 1
	print(sum_full - (sum_powers << 1))

t = int(input())
for i in range(t):
    n = int(input())
    result = n * (n + 1) // 2
    j = 1
    while j <= n:
        result -= 2 * j
        j *= 2
    print(result)

import math
t = int(input())
for i in range(t):
	k = int(input())
	ans = k * (k + 1) // 2
	pw = 2 ** (math.floor(math.log2(k)) + 1) - 1
	print(ans - 2 * pw)

T = int(input())

for t in range(T):
    n = int(input())
    sum = n * (n + 1) // 2
    x = 1
    while x <= n:
        sum -= 2 * x
        x *= 2
    print(sum)


def log2(n):
    i = 1
    while i <= n:
        i *= 2
    return i

t = int(input())
for i in range(t):
    n = int(input())
    print(n*(n+1)//2 - 2*(log2(n)-1))


t = int(input())
for i in range(t):
    n = int(input())
    summ = (n + 1) * (n // 2)
    if (n % 2 != 0): summ += (n + 1) // 2
    x = 1
    while x <= n:
        summ -= 2 * x
        x *= 2
    print(summ)


n = int(input())
degs = [1]
cur = 1
while (cur < 1000000000):
    cur *= 2
    degs.append(cur)
for _ in range(n):
    k = int(input())
    ar = k * (k + 1) // 2
    #print(ar)
    pos = 0
    while degs[pos] <= k:
        pos += 1
    geom = 2 ** pos - 1
    #print(geom)
    print(ar -2 * geom)


def solve():
    n = int(input())
    sm = (1 + n) * n // 2
    i = 1
    while i <= 1073741824:
        if i <= n:
            sm -= 2*i
        else:
            break
        i *= 2
    print(sm)
t = int(input())
for i in range(t):
    solve()


def main():
    sm = 0
    a = [ 2**i for i in range(31)]
    t = int(input())
    for j in range(t):
        n = int(input())
        sm = n * (n + 1) // 2
        i = 0
        while a[i] <= n:
            sm-= 2*a[i]
            i += 1
        print(sm)


main()
    


t = int(input())
for _ in range(t):
    inp = int(input())
    print(inp * (inp + 1) // 2 - 2 * (2 ** (len(bin(inp)) - 2) - 1))


T = int(input())

for _ in range(T):
  N = int(input())
  tmpN = N
  p = 0
  while tmpN > 0:
    tmpN = tmpN >> 1
    p += 1

  x = N*(N+1)//2
  y = (1 << (p+1))-2
  print(x-y)

from math import log2
t = int(input())

for _ in range(t):
	n = int(input())
	k = int(log2(n))
	ans = n * (n+1) // 2  # sum all from 1 to n
	ans -= 2 * (2**(k+1) - 1)  # subtract twice sum of 2^n for n from 0 to k

	print(ans)