Our little friend-person Bico loves writing numbers on the blackboard in their room. One day they come up with a game of writing odd numbers. To play this game, one should start writing odd numbers from one. On each line, there must be an odd number of odd numbers written, in the amount of the next odd number. Bico's blackboard looks like the following:

1
3 5 7
9 11 13 15 17

Can you help our little friend Bico to find the sum of the last 3 numbers on the line where they have written \(\mathbf{N_i}\) numbers?

Input

First line consists of integer \(\mathbf{T}\), number of test cases.

Each of the next \(\mathbf{T}\) lines has integer \(\mathbf{N_i}\) being the number of odd numbers written in the line being asked.

Batch #1:

• \(1 \leq \mathbf{T} \leq 200\)
• \(3 \leq \mathbf{N_i} < 10^{9}\)

Batch #2:

• \(1 \leq \mathbf{T} \leq 6 \cdot 10^{4}\)
• \(3 \leq \mathbf{N_i} < 10^{9}\)

Output

In \(\mathbf{T}\) lines, the answer of the corresponding test case, sum of the last 3 numbers on the line that has \(\mathbf{N_i}\) numbers.

Examples

Input:

1
9

Output:

141

Input:

3
3
5
7

Output:

15
45
87

Explanation:

1st Input

First input has one test case that asks for the sum of last 3 numbers of the line where 9 numbers are written. The first 5 lines of the blackboard look like the following:

1
3 5 7
9 11 13 15 17
19 21 23 25 27 29 31
33 35 37 39 41 43 45 47 49

The line with 9 odd numbers have the last 3 numbers 45, 47, 49. Sum of the three is 141.

2nd Input

Second input has three test cases that asks for the sum of last 3 numbers of the line where 3, 5 and 7 numbers are written. The first 4 lines of the blackboard look like the following:

1
3 5 7
9 11 13 15 17
19 21 23 25 27 29 31

For the first test case, last three numbers on the second line 3, 5 and 7 has sum 15. For the second test case, last three numbers on the third line 13, 15 and 17 has sum 45. For the third test case, last three numbers on the forth line 45, 47 and 49 has sum 87.