Permutation Xor Sum solution|Codesheff lunchtime 2022 for div 3

For a permutation P$P$ of integers from 1$1$ to N$N$, let's define its value as (1⊕P1)+(2⊕P2)+…+(N⊕PN)$(1\oplus P_1)+(2\oplus P_2)+\dots +(N\oplus P_N)$.

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

As a reminder, ⊕$\oplus$ denotes the bitwise XOR operation

Input Format

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

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

Output Format

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

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤109$1\le N\le {10}^9$.

Subtasks

Subtask 1 (60 points): The sum of N$N$ over all test cases doesn't exceed 106${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

For N=1$N=1$, the only such permutation is P=(1)$P=(1)$, its value is 1⊕1=0$1\oplus 1=0$.

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

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

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

Solution:

This question solution is updated within contest time. please click on follow button and subscribe our channel.if you follow and subscribe our channel then get notification of answer as soon as possible.