Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Settlers of Catan
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 377Accepted: 186

Description

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:
1. the new tile must be different from its neighboring tiles on the board so far;
2. in case multiple tiles are possible, we choose a resource that occurs the least number of times on the board so far;
3. 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 nth tile that is added to the board (starting with n = 1).

Input

On the first line of the input there is one integer c (1 <= c <= 200), the number of test cases. Each following test case consists of a single line with one integer n (1 <= n <= 10 000), the number of the tile we are curious about.

Output

For each test case, print a single line with one integer, specifying the resource of the nth tile.

Sample Input

4
1
4
10
100

Sample Output

1
4
5
5

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator