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.

  <-- 12
4 3 2 11
5 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

The first line of the input contains a single integer n(<=10000), this is the number of test cases. This is followed by n lines each containing a single integer(<=10000).

Output

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