Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3470
Magic Squares

Time Limit: 2 Seconds      Memory Limit: 65536 KB

One day, the astronauts from China arrived in a planet that they have never been before. First, they sent a robot called AAA to explore the environment as usual.

However, AAA became confused as soon as it departed from the aerostat: it found that the surface of the planet was divided into many blocks we call magic squares, each block is marked by an unique integer in a special order(as shown in the left graph). Fortunately, AAA is so clever that it soon found the relationship between these blocks and the Descartes coordinate system (as shown in the right graph).

Before each movement, AAA would send its current block number to the monitor, then move to the right position the monitor order it to. Assuming that the monitor would only order AAA to move to the block neighbored to the current block. We say two blocks are neighbor if they share one same edge.

To complete the task in time, the monitor need to respond to the request of the robot as soon as possible. But the computing progress may be too complicated for beings. So they now turn to you, an excellent programmer, help them list the blocks the AAA can reach at the time in order to sent command to the robot in a short time.


The first line of input is the number of test cases T, then T lines follow, each is a test case with only one positive integers n no larger than 2,000,000,000.


The output consists of exactly T lines, one line for each case.
Line i (1 <= i <= T) should contain an increasing sequence of integers separated by single spaces -- the numbers of the blocks that the robot could reach (with its current block numbered n).

Sample Input


Sample Output

4 6 16 18

Author: HE, Xing
Contest: ZOJ Monthly, February 2011
Submit    Status