This problem contains Breaking Bad TV series spoilers. If you haven't watched season 5 so far, you can skip this problem to avoid spoilers.
We're done when I say we're done. - Walter White to Saul Goodman
After killing Gus Fring, Walter White and Jesse Pinkman are planning to run their own Methamphetamine business.
One month, they produced a batch of Methamphetamine which has an interesting property. It contains all amount of packets from $1$ to $n$ distinctly. As the business is risky, their lawyer Saul Goodman wants to know the oddness of the batch.
To calculate the oddness of the batch, first you have to arrange all meth packets from $1$ to $n$ serially in an array. The oddness of the batch is the number of the subarrays which contains an odd sum in this array. For example, there are $4$ meth packets in the batch. So, the array will be like $\{1,2,3,4\}$. There are 6 subarrays which contains an odd sum: $\{1\}, \{3\}, \{1,2\}, \{2, 3\}, \{3, 4\}, \{2, 3, 4\}$. So, the oddness of the batch is $6$.
Can you help Saul Goodman?
The input consists of multiple test cases.
The first line contains an integer $t$ $(1 \leq t \leq 5000)$ — the number of test cases.
Each of the next $t$ lines contains an integer $n$ $(1 \leq n \leq 10^{7})$ — the number of packets.
In a single line, output the oddness of the batch.
| Input | Output |
|---|---|
5 1 4 5 10 36 | 1 6 9 30 342 |