카탄의 개척자

"카탄의 개척자"는 많은 사람들이 즐기는 보드게임이다. 게임을 시작하려면, 먼저 게임판을 랜덤으로 만들어야 한다. 게임판은 육각형 타일로 이루어져 있으며, 각 타일은 자원을 하나씩 포함하고 있다. 자원은 총 다섯 가지 종류가 있으며, 점토, 재목, 양모, 곡물, 광석이다. 각 자원은 1부터 5까지 순서로 나타낼 수 있다.

랜덤을 이용해서 게임판을 만들면, 같은 자원이 인접한 타일에 있는 경우가 있을 수도 있다. 이런 배치를 매우 싫어하는 사람이 많다. 따라서, 다음과 같은 과정으로 게임판을 만들려고 한다. 먼저, 게임판의 중앙에서 만들기를 시작하고, 나선 형태로 진행한다.

• 새로운 타일은 이미 채워진 인접한 타일에 들어있는 자원과 다른 자원이어야 한다.
• 가능한 자원이 여러 가지인 경우에는, 보드에 가장 적게 나타난 자원을 선택한다.
• 그러한 경우도 여러 가지라면, 번호가 작은 것을 선택한다.

아래 그림은 어떻게 나선 형태로 진행하는지와, 어떤 자원을 선택하는지를 나타낸 그림이다. n번째로 채우는 타일에 어떤 자원을 선택하는지 고르는 프로그램을 작성하시오. (n은 1부터 시작한다)

첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. (1 ≤ n ≤ 10000)

n번째 타일에 들어있는 자원을 출력한다.