• # For Solution

For a permutation PP of integers from 11 to NN, let’s define its value as (1P1)+(2P2)++(NPN)(1⊕P1)+(2⊕P2)+…+(N⊕PN).

Given NN, find the maximum possible value of the permutation of integers from 11 to NN.

As a reminder,  denotes the bitwise XOR operation

### Input Format Permutation XOR Sum solution codechef

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

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

### Output Format

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

### Constraints Permutation XOR Sum solution codechef

• 1T1051≤T≤105
• 1N1091≤N≤109.

Subtask 1 (60 points): The sum of NN over all test cases doesn’t exceed 106106Subtask 2 (40 points): No additional constraints.

### Sample Input 1

5
1
2
3
4
29012022


### Sample Output 1

0
6
6
20
841697449540506


### Explanation Permutation XOR Sum solution codechef

For N=1N=1, the only such permutation is P=(1)P=(1), its value is 11=01⊕1=0.

For N=2N=2, the permutation with the best value is P=(2,1)P=(2,1), with value 12+21=61⊕2+2⊕1=6.

For N=3N=3, the permutation with the best value is P=(2,1,3)P=(2,1,3), with value 12+21+33=61⊕2+2⊕1+3⊕3=6.

For N=4N=4, the permutation with the best value is P=(2,1,4,3)P=(2,1,4,3), with value 12+21+34+43=201⊕2+2⊕1+3⊕4+4⊕3=20.