Sum of Series with Conditional Terms

You are given an integer n and you need to compute the sum of the first n terms of a sequence where the i-th term is defined as follows:

\( a_i = \begin{cases} i, & \text{if } i \text{ is odd} \\ i^2, & \text{if } i \text{ is even} \end{cases}\)

Your task is to calculate the sum \( S(n) = \sum_{i=1}^{n} a_i \) for each provided test case.

Input will be provided via standard input (stdin) and the output should be printed to standard output (stdout). Make sure your program handles multiple test cases in one run.

inputFormat

The first line of input contains a single integer T (1 ≤ T ≤ 10⁵), the number of test cases. Each of the next T lines contains a single integer n (1 ≤ n ≤ 10⁷), indicating the number of terms in the series.

outputFormat

For each test case, output a single line containing the sum \( S(n) \) computed as per the rules described above.

## sample

3
1
2
5

1
5
29

</p>