시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 233 79 62 32.632%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

4
1
4
10
100

예제 출력 1

1
4
5
5
W3sicHJvYmxlbV9pZCI6IjM2NzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWQwYzRcdWM3NTggXHVhYzFjXHVjYzk5XHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD4mcXVvdDtcdWNlNzRcdWQwYzRcdWM3NTggXHVhYzFjXHVjYzk5XHVjNzkwJnF1b3Q7XHViMjk0IFx1YjljZVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjOTkwXHVhZTMwXHViMjk0IFx1YmNmNFx1YjRkY1x1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjgyNFx1YmE3NCwgXHViYTNjXHVjODAwIFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0NCBcdWI3OWNcdWIzNjRcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzQwIFx1YzcyMVx1YWMwMVx1ZDYxNSBcdWQwYzBcdWM3N2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1ZDBjMFx1Yzc3Y1x1Yzc0MCBcdWM3OTBcdWM2ZDBcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc5MFx1YzZkMFx1Yzc0MCBcdWNkMWQgXHViMmU0XHVjMTJmIFx1YWMwMFx1YzljMCBcdWM4ODVcdWI5NThcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM4MTBcdWQxYTAsIFx1YzdhY1x1YmFhOSwgXHVjNTkxXHViYWE4LCBcdWFjZTFcdWJiM2MsIFx1YWQxMVx1YzExZFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1Yzc5MFx1YzZkMFx1Yzc0MCAxXHViZDgwXHVkMTMwIDVcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI3OWNcdWIzNjRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWJhNzQsIFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM2ZDBcdWM3NzQgXHVjNzc4XHVjODExXHVkNTVjIFx1ZDBjMFx1Yzc3Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZjAgXHViYzMwXHVjZTU4XHViOTdjIFx1YjllNFx1YzZiMCBcdWMyZWJcdWM1YjRcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1YjljZVx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1YzczY1x1Yjg1YyBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NDQgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHVjOTExXHVjNTU5XHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjk3YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjZTAsIFx1YjA5OFx1YzEyMCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQwYzBcdWM3N2NcdWM3NDAgXHVjNzc0XHViYmY4IFx1Y2M0NFx1YzZjY1x1YzljNCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVkMGMwXHVjNzdjXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWM2ZDBcdWFjZmMgXHViMmU0XHViOTc4IFx1Yzc5MFx1YzZkMFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM3OTBcdWM2ZDBcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgXHViY2Y0XHViNGRjXHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHViMDk4XHVkMGMwXHViMDljIFx1Yzc5MFx1YzZkMFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM1YjRcdWI1YmJcdWFjOGMgXHViMDk4XHVjMTIwIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWIyOTRcdWM5YzBcdWM2NDAsIFx1YzViNFx1YjVhNCBcdWM3OTBcdWM2ZDBcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFkZjhcdWI5YmNcdWM3NzRcdWIyZTQuIG5cdWJjODhcdWM5ZjhcdWI4NWMgXHVjYzQ0XHVjNmIwXHViMjk0IFx1ZDBjMFx1Yzc3Y1x1YzVkMCBcdWM1YjRcdWI1YTQgXHVjNzkwXHVjNmQwXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFjZTBcdWI5NzRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gKG5cdWM3NDAgMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc2V0dGxlci5wbmdcIiBzdHlsZT1cImhlaWdodDoyODBweDsgd2lkdGg6MzI5cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggYyAoMSAmbGU7IGMgJmxlOyAyMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPm5cdWJjODhcdWM5ZjggXHVkMGMwXHVjNzdjXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWM2ZDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZXR0bGVycyBvZiBDYXRhbiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHBvcHVsYXIgYm9hcmQgZ2FtZSAmcXVvdDtTZXR0bGVycyBvZiBDYXRhbiZxdW90OyBzdGFydHMgYnkgY3JlYXRpbmcgYSByYW5kb20gYm9hcmQuIFRoaXMgYm9hcmQgY29uc2lzdHMgb2YgaGV4YWdvbmFsIHJlc291cmNlIHRpbGVzIGNvbnRhaW5pbmcgZml2ZSBkaWZmZXJlbnQgcmVzb3VyY2VzOiBjbGF5LCBsdW1iZXIsIHdvb2wsIGdyYWluLCBhbmQgb3JlLiBGb3Igc2ltcGxpY2l0eSwgd2Ugd2lsbCBkZW5vdGUgdGhlc2UgYnkgdGhlIG51bWJlcnMgMSB0byA1LjxcL3A+XHJcblxyXG48cD5SYW5kb20gYm9hcmRzLCBob3dldmVyLCBvZnRlbiBoYXZlIG11bHRpcGxlIGVxdWFsIHJlc291cmNlIHRpbGVzIG5leHQgdG8gZWFjaCBvdGhlci4gVGhpcyBhbm5veXMgc29tZSBwbGF5ZXJzLiBUaGVyZWZvcmUsIHdlIGhhdmUgaW52ZW50ZWQgYSBuZXcgd2F5IG9mIGNyZWF0aW5nIHRoZSBwbGF5aW5nIGJvYXJkLiBTdGFydGluZyBpbiB0aGUgbWlkZGxlIGFuZCBzcGlyYWxpbmcgb3V0d2FyZHMsIGVhY2ggdGltZSB3ZSBhZGQgYSBuZXcgdGlsZSB0byB0aGUgYm9hcmQgd2UgY2hvb3NlIHRoZSByZXNvdXJjZSBvZiB0aGUgdGlsZSBhY2NvcmRpbmcgdG8gdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgbmV3IHRpbGUgbXVzdCBiZSBkaWZmZXJlbnQgZnJvbSBpdHMgbmVpZ2hib3JpbmcgdGlsZXMgb24gdGhlIGJvYXJkIHNvIGZhcjs8XC9saT5cclxuXHQ8bGk+aW4gY2FzZSBtdWx0aXBsZSB0aWxlcyBhcmUgcG9zc2libGUsIHdlIGNob29zZSBhIHJlc291cmNlIHRoYXQgb2NjdXJzIHRoZSBsZWFzdCBudW1iZXIgb2YgdGltZXMgb24gdGhlIGJvYXJkIHNvIGZhcjs8XC9saT5cclxuXHQ8bGk+aW4gY2FzZSBtdWx0aXBsZSB0aWxlcyBhcmUgc3RpbGwgcG9zc2libGUsIHRoZSBuZXcgcmVzb3VyY2UgbXVzdCBoYXZlIHRoZSBsb3dlc3QgbnVtYmVyIHBvc3NpYmxlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBmaWd1cmUgdW5kZXJuZWF0aCBzaG93cyBob3cgdG8gc3BpcmFsIG91dHdhcmRzIGFuZCB3aGljaCByZXNvdXJjZSB0aWxlcyBhcmUgY2hvc2VuIGZpcnN0LiBXZSBhcmUgY3VyaW91cyB3aGF0IHRoZSBudW1iZXIgb2YgdGhlIHJlc291cmNlIGlzIG9uIHRoZSBudGggdGlsZSB0aGF0IGlzIGFkZGVkIHRvIHRoZSBib2FyZCAoc3RhcnRpbmcgd2l0aCBuID0gMSkuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc2V0dGxlci5wbmdcIiBzdHlsZT1cImhlaWdodDoyODBweDsgd2lkdGg6MzI5cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCB0aGVyZSBpcyBvbmUgaW50ZWdlciBjICgxICZsZTsgYyAmbGU7IDIwMCksIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCBmb2xsb3dpbmcgdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgd2l0aCBvbmUgaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDEwIDAwMCksIHRoZSBudW1iZXIgb2YgdGhlIHRpbGUgd2UgYXJlIGN1cmlvdXMgYWJvdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBhIHNpbmdsZSBsaW5lIHdpdGggb25lIGludGVnZXIsIHNwZWNpZnlpbmcgdGhlIHJlc291cmNlIG9mIHRoZSBudGggdGlsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=