The popular board game “Settlers of Catan” starts by
creating a random board. This board consists of hexagonal
resource tiles containing five different resources: clay,
lumber, wool, grain, and ore. For simplicity, we will denote
these by the numbers 1 to 5.
Random boards, however, often have multiple equal resource
tiles next to each other. This annoys some players. Therefore,
we have invented a new way of creating the playing board.
Starting in the middle and spiraling outwards, each time we add
a new tile to the board we choose the resource of the tile
according to the following rules:
the new tile must be different from its neighboring
tiles on the board so far;
in case multiple tiles are possible, we choose a
resource that occurs the least number of times on the board
in case multiple tiles are still possible, the new
resource must have the lowest number possible.
The figure underneath shows how to spiral outwards and which
resource tiles are chosen first. We are curious what the number
of the resource is on the $n$th tile that is added to the board
(starting with $n=1$).
On the first line of the input there is one integer
$c$ $(1 \le c \le 200)$, the number of
test cases. Each following test case consists of a single line
with one integer $n$
$(1 \le n \le 10\, 000)$,
the number of the tile we are curious about.
For each test case, print a single line with one integer,
specifying the resource of the $n$th tile.
|Sample Input 1
||Sample Output 1