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

见题面

见题面