유명 보드 게임 "카탄의 개척자"를 시작하기 위해서는 무작위 보드를 생성해야 합니다. 무작위 보드는 다섯 종류의 다른 자원 - 점토, 나무, 양, 밀, 철 - 이 있는 육각형 모양 자원 칸으로 이루어집니다. 쉬운 이해를 위해 각 자원에 1부터 5까지 번호를 붙입시다.
보드를 무작위로 생성하면 여러 개의 같은 자원 칸이 옆에 붙는 일이 종종 생기는데, 그러면 플레이어는 짜증이 납니다. 따라서 보드를 생성하는 새 방법을 고안했습니다. 가운데에서 시작해 회오리 모양으로 바깥으로 뻗어 나가며, 아래의 규칙에 따라 자원을 고르고 해당 칸을 보드에 추가합니다.
새 자원 칸은 그때까지 보드에 놓인 이웃하는 자원 칸과 모두 달라야 합니다.
여러 자원 칸이 가능할 경우, 그때까지 보드에 등장한 횟수가 가장 적은 자원을 선택합니다.
여전히 여러 자원 칸이 가능할 경우, 가장 낮은 번호의 자원을 선택합니다.
아래 그림은 어떻게 바깥으로 뻗어 나가며, 어떤 자원 칸이 우선 선택되는지 나타냅니다. (N = 1부터 시작할 때) 보드에 N번째 놓이는 자원 칸의 자원 번호를 알아냅시다.
입력
첫 줄에 테스트 케이스의 수를 나타내는 하나의 정수 c가 주어집니다 (1 <= c <= 200). 이후 각 테스트 케이스마다 궁금한 칸의 번호를 나타내는 하나의 정수 n이 한 줄에 주어집니다 (1 <= n <= 10000).
출력
각 테스트 케이스에 대해, N번째 칸의 자원을 나타내는 하나의 정수를 한 줄에 출력합시다.
ez_code 7달 전
문제
유명 보드 게임 "카탄의 개척자"를 시작하기 위해서는 무작위 보드를 생성해야 합니다. 무작위 보드는 다섯 종류의 다른 자원 - 점토, 나무, 양, 밀, 철 - 이 있는 육각형 모양 자원 칸으로 이루어집니다. 쉬운 이해를 위해 각 자원에 1부터 5까지 번호를 붙입시다.
보드를 무작위로 생성하면 여러 개의 같은 자원 칸이 옆에 붙는 일이 종종 생기는데, 그러면 플레이어는 짜증이 납니다. 따라서 보드를 생성하는 새 방법을 고안했습니다. 가운데에서 시작해 회오리 모양으로 바깥으로 뻗어 나가며, 아래의 규칙에 따라 자원을 고르고 해당 칸을 보드에 추가합니다.
아래 그림은 어떻게 바깥으로 뻗어 나가며, 어떤 자원 칸이 우선 선택되는지 나타냅니다. (N = 1부터 시작할 때) 보드에 N번째 놓이는 자원 칸의 자원 번호를 알아냅시다.
입력
첫 줄에 테스트 케이스의 수를 나타내는 하나의 정수 c가 주어집니다 (1 <= c <= 200). 이후 각 테스트 케이스마다 궁금한 칸의 번호를 나타내는 하나의 정수 n이 한 줄에 주어집니다 (1 <= n <= 10000).
출력
각 테스트 케이스에 대해, N번째 칸의 자원을 나타내는 하나의 정수를 한 줄에 출력합시다.