카탄의 개척자

'카탄의 개척자'는 여러 사람이 즐기는 보드게임이다. 게임을 시작하려면 먼저 게임판을 만들어야 한다. 게임판은 육각형 타일들로 이루어지며, 각 타일에는 자원이 하나씩 놓인다. 자원은 점토, 재목, 양모, 곡물, 광석의 다섯 종류이고, 차례대로 $1$부터 $5$까지의 번호로 나타낸다.

타일을 아무렇게나 놓으면 같은 자원이 서로 맞닿는 경우가 생기는데, 많은 사람이 이런 배치를 싫어한다. 그래서 다음 방법으로 게임판을 채운다. 가장 먼저 게임판 중앙에 첫 번째 타일을 놓고, 그 타일을 감싸며 육각형 고리 모양으로 바깥을 향해 나선을 그리듯 한 칸씩 이어서 채워 나간다. 한 고리를 모두 채우면 바깥으로 한 칸 나가 같은 방향으로 계속 감아 나가며, 이렇게 나선은 끊기지 않는 하나의 연속된 경로를 이룬다.

새로 놓는 타일의 자원은 다음 규칙으로 정한다.

• 이미 채워져 인접해 있는 타일들의 자원과는 모두 달라야 한다.
• 그런 자원이 여러 가지이면, 지금까지 게임판에 가장 적게 놓인 자원을 고른다.
• 그래도 여러 가지이면, 번호가 가장 작은 자원을 고른다.

이 규칙에 따라 타일을 채울 때, $n$번째로 놓이는 타일의 자원을 구하는 프로그램을 작성하시오. (타일의 번호는 $1$번부터 시작한다.)

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

각 테스트 케이스마다 $n$번째 타일에 놓이는 자원의 번호를 한 줄에 하나씩 출력한다.