• For Solution

Given an integer NN, consider all arrays AA of size NN such that:

• All the elements are non-negative and distinct.
• All prefix sums are odd. Formally, for all ii such that 1iN1≤i≤Nij=1Ai∑j=1iAi is odd.

Among all possible arrays AA, output the smallest possible sum of the elements of the array.

Note: Since the Input/Output may be large, it is preferred to use fast I/O.

Odd Sum solution codechef

• The first line contains TT – the number of test cases. Then the test cases follow.
• The first line of each test case contains NN – the size of the array.

Odd Sum solution codechef

For each test case, output on one line the smallest sum among all arrays satisfying the constraints.

Odd Sum solution codechef

• 1T1061≤T≤106
• 1N1091≤N≤109

Sample Input 1

1
3


Odd Sum solution codechef

3


Explanation

• Test case 11: A possible array is [1,2,0][1,2,0][1,0,0][1,0,0] is not valid because 00 occurs twice in it; [0,1,2][0,1,2] is not valid because the prefix sum until the first index is 00, which is even. Another possible array is [5,2,4][5,2,4][1,2,0][1,2,0] yields the sum 33, and we can prove that there are no valid arrays that have sum less than 33.