Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Spoiler Alert

By rezaulhsagar · Limits 10s, 32 MB

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 11 to nn 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 11 to nn 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 44 meth packets in the batch. So, the array will be like {1,2,3,4}\{1,2,3,4\}. There are 6 subarrays which contains an odd sum: {1},{3},{1,2},{2,3},{3,4},{2,3,4}\{1\}, \{3\}, \{1,2\}, \{2, 3\}, \{3, 4\}, \{2, 3, 4\}. So, the oddness of the batch is 66.

Can you help Saul Goodman?

Input

The input consists of multiple test cases.
The first line contains an integer tt (1t5000)(1 \leq t \leq 5000) — the number of test cases.
Each of the next tt lines contains an integer nn (1n107)(1 \leq n \leq 10^{7}) — the number of packets.

Output

In a single line, output the oddness of the batch.

Sample

InputOutput
5
1
4
5
10
36
1
6
9
30
342

    Discussion

    Statistics


    85% Solution Ratio

    sunkuet02Earliest, Jul '20

    KabbyaFastest, 0.0s

    sunkuet02Lightest, 131 kB

    bokaifShortest, 54B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.