SPRLNMS - Spiral numbers

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 nth 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

Added by:shivamrana
Date:2012-02-11
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Dementia 2012

hide comments
2012-05-20 13:46:46 (Tjandra Satria Gunawan)(曾毅昆)
I solved this problem with only 94B of source length... ;-)
2012-02-11 14:29:52 Aradhya
very tough question..uff finally gt AC..
this q demoralisd me!!
2012-02-11 14:29:52 maaz
Kids here is a treat 4 u!!
Enjoy it!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.