Dennis is programming a robot that is supposed to paint a horizontal line. Not being one to care much about efficiency, Dennis programs the robot to move in an anti-clockwise spiral as shown below.

0 1 10
6 7 8 9

The robot starts at position zero, then moves to position 1, then position 2 and so on. Dennis wants all of the tiles to the right of 0 to be painted black. (These tiles are represented as bold numbers in the figure above.)
Your task is to help Dennis by telling him which is the n^th tile that must be painted black, with the zeroth tile being zero.

Input Format
The first line of the input contains a single integer n, this is the number of test cases. This is followed by n lines each containing a single integer.

Output Format
For each test case output a single integer which is the number of the tile that corresponds to the nth tile that must be painted.

Example
Input

3
0
1
2

Output

0
1
10

见题面

见题面