Mandark thinks he is better than Dexter. He challenges Dexter to find answer to a mathematics problem he created. Dexter accepts the challenge and decides to write a program for it to reduce manual calculations.

The problem: Let f(x) be the greatest odd divisor of x, where x is a positive integer. You are given a positive integer X. Calculate f(1)+f(2)+...+f(X).

INPUT

First line of input gives T, the number of test cases.
T lines follow, each having X as input positive integer.

OUTPUT

Print value of f(1)+f(2)+...+f(X) for each test case.

CONSTRAINTS
1 ≤ T ≤ 50
X will be between 1 and 1000000000, inclusive.

SAMPLE INPUT
2
7
777

SAMPLE OUTPUT
21
201537

Explanation

For first case, f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7)=1+1+3+1+5+3+7=21

Similarly, f(1)+f(2)+...+f(777) = 201537

见题面

见题面