Alice is playing Minecraft with Bob. She wants to build a beacon made of diamond blocks so enormous that she even added a mod to set the building height limit of the game to infinite. However, she realized she has zero diamonds in her base. Therefore, she wonders how many diamonds are needed to build the beacon.

Note that a beacon is a pyramid structure made of many layers, the first layer is the beacon, the second layer is a $3 \times 3$ diamond block structure, the third layer is a $5 \times 5$ block structure and so on. Also, $1$ diamond block is crafted by $9$ diamonds.

Input

The first line contains a positive integer $Q$, the number of queries Alice wonders.
The next $Q$ lines each contain a positive integer $N$, which is the number of layers of the beacon.

Output

Output $Q$ lines. Each line should contain a single integer representing the total number of diamonds Alice needs to to build an $N$-layer beacon.

Subtasks

For all test cases,
$1 \le Q, N \le 10^5$

Subtask 1 (25 pts): $Q = 1, 1 \le N \le 5$
Subtask 2 (25 pts): $1 \le Q, N \le 500$
Subtask 3 (25 pts): $Q = 1$
Subtask 4 (25 pts): No additional constraints