Settlers of Catan

Time limit1sMemory limit128 MB

Summary

Simulate filling hexagonal tiles in an outward spiral with resource-choice rules and report the resource of the n-th tile.

Level: Medium6 of 10
Topics: Simulation, Implementation, Geometry
Solved: No attempts yet

Problem

'Settlers of Catan' is a board game enjoyed by many people. To start a game you must first build the board. The board is made of hexagonal tiles, and each tile holds exactly one resource. There are five kinds of resources — clay, lumber, wool, grain, and ore — numbered $1$ through $5$ in that order.

Placing tiles at random can leave identical resources touching each other, which many players dislike. So the board is filled as follows. The first tile is placed at the center of the board, and from there the board is filled one tile at a time in a hexagonal spiral that winds outward around the center. Once a full ring is completed, the spiral steps one tile outward and keeps winding in the same direction, so the whole spiral is a single continuous, unbroken path.

The resource of each newly placed tile is decided by these rules:

It must differ from the resources of every already-placed tile adjacent to it.
If several resources are allowed, choose the one placed the fewest times on the board so far.
If there is still a tie, choose the resource with the smallest number.

Following these rules, write a program that finds the resource of the $n$ -th placed tile. (Tiles are numbered starting from $1$ .)

Input

The first line contains the number of test cases $c$ $(1 \le c \le 200)$ . Each of the following test cases consists of a single line containing an integer $n$ $(1 \le n \le 10000)$ .

Output

For each test case, print the number of the resource placed on the $n$ -th tile, one per line.

Examples4

Example 1
Input
```
4
1
4
10
100
```
Expected output
```
1
4
5
5
```
Example 2
Input
```
7
1
2
3
4
5
6
7
```
Expected output
```
1
2
3
4
5
2
3
```
Example 3
Input
```
1
1
```
Expected output
```
1
```
Example 4
Input
```
6
2
4
6
8
50
500
```
Expected output
```
2
4
2
1
5
4
```