시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 242 83 65 32.995%

문제

"카탄의 개척자"는 많은 사람들이 즐기는 보드게임이다. 게임을 시작하려면, 먼저 게임판을 랜덤으로 만들어야 한다. 게임판은 육각형 타일로 이루어져 있으며, 각 타일은 자원을 하나씩 포함하고 있다. 자원은 총 다섯 가지 종류가 있으며, 점토, 재목, 양모, 곡물, 광석이다. 각 자원은 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+XHJcblx0PGxpPlx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM3OTBcdWM2ZDBcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQsIFx1YmNmNFx1YjRkY1x1YzVkMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVhYzhjIFx1YjA5OFx1ZDBjMFx1YjA5YyBcdWM3OTBcdWM2ZDBcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YzViNFx1YjViYlx1YWM4YyBcdWIwOThcdWMxMjAgXHVkNjE1XHVkMGRjXHViODVjIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YjI5NFx1YzljMFx1YzY0MCwgXHVjNWI0XHViNWE0IFx1Yzc5MFx1YzZkMFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YWRmOFx1YjliY1x1Yzc3NFx1YjJlNC4gblx1YmM4OFx1YzlmOFx1Yjg1YyBcdWNjNDRcdWM2YjBcdWIyOTQgXHVkMGMwXHVjNzdjXHVjNWQwIFx1YzViNFx1YjVhNCBcdWM3OTBcdWM2ZDBcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0XHVjOWMwIFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiAoblx1Yzc0MCAxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNCk8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zZXR0bGVyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI4MHB4OyB3aWR0aDozMjlweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBjICgxICZsZTsgYyAmbGU7IDIwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+blx1YmM4OFx1YzlmOCBcdWQwYzBcdWM3N2NcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1Yzc5MFx1YzZkMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNldHRsZXJzIG9mIENhdGFuIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgcG9wdWxhciBib2FyZCBnYW1lICZxdW90O1NldHRsZXJzIG9mIENhdGFuJnF1b3Q7IHN0YXJ0cyBieSBjcmVhdGluZyBhIHJhbmRvbSBib2FyZC4gVGhpcyBib2FyZCBjb25zaXN0cyBvZiBoZXhhZ29uYWwgcmVzb3VyY2UgdGlsZXMgY29udGFpbmluZyBmaXZlIGRpZmZlcmVudCByZXNvdXJjZXM6IGNsYXksIGx1bWJlciwgd29vbCwgZ3JhaW4sIGFuZCBvcmUuIEZvciBzaW1wbGljaXR5LCB3ZSB3aWxsIGRlbm90ZSB0aGVzZSBieSB0aGUgbnVtYmVycyAxIHRvIDUuPFwvcD5cclxuXHJcbjxwPlJhbmRvbSBib2FyZHMsIGhvd2V2ZXIsIG9mdGVuIGhhdmUgbXVsdGlwbGUgZXF1YWwgcmVzb3VyY2UgdGlsZXMgbmV4dCB0byBlYWNoIG90aGVyLiBUaGlzIGFubm95cyBzb21lIHBsYXllcnMuIFRoZXJlZm9yZSwgd2UgaGF2ZSBpbnZlbnRlZCBhIG5ldyB3YXkgb2YgY3JlYXRpbmcgdGhlIHBsYXlpbmcgYm9hcmQuIFN0YXJ0aW5nIGluIHRoZSBtaWRkbGUgYW5kIHNwaXJhbGluZyBvdXR3YXJkcywgZWFjaCB0aW1lIHdlIGFkZCBhIG5ldyB0aWxlIHRvIHRoZSBib2FyZCB3ZSBjaG9vc2UgdGhlIHJlc291cmNlIG9mIHRoZSB0aWxlIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnRoZSBuZXcgdGlsZSBtdXN0IGJlIGRpZmZlcmVudCBmcm9tIGl0cyBuZWlnaGJvcmluZyB0aWxlcyBvbiB0aGUgYm9hcmQgc28gZmFyOzxcL2xpPlxyXG5cdDxsaT5pbiBjYXNlIG11bHRpcGxlIHRpbGVzIGFyZSBwb3NzaWJsZSwgd2UgY2hvb3NlIGEgcmVzb3VyY2UgdGhhdCBvY2N1cnMgdGhlIGxlYXN0IG51bWJlciBvZiB0aW1lcyBvbiB0aGUgYm9hcmQgc28gZmFyOzxcL2xpPlxyXG5cdDxsaT5pbiBjYXNlIG11bHRpcGxlIHRpbGVzIGFyZSBzdGlsbCBwb3NzaWJsZSwgdGhlIG5ldyByZXNvdXJjZSBtdXN0IGhhdmUgdGhlIGxvd2VzdCBudW1iZXIgcG9zc2libGUuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGZpZ3VyZSB1bmRlcm5lYXRoIHNob3dzIGhvdyB0byBzcGlyYWwgb3V0d2FyZHMgYW5kIHdoaWNoIHJlc291cmNlIHRpbGVzIGFyZSBjaG9zZW4gZmlyc3QuIFdlIGFyZSBjdXJpb3VzIHdoYXQgdGhlIG51bWJlciBvZiB0aGUgcmVzb3VyY2UgaXMgb24gdGhlIG50aCB0aWxlIHRoYXQgaXMgYWRkZWQgdG8gdGhlIGJvYXJkIChzdGFydGluZyB3aXRoIG4gPSAxKS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zZXR0bGVyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI4MHB4OyB3aWR0aDozMjlweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IHRoZXJlIGlzIG9uZSBpbnRlZ2VyIGMgKDEgJmxlOyBjICZsZTsgMjAwKSwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIGZvbGxvd2luZyB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSB3aXRoIG9uZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMTAgMDAwKSwgdGhlIG51bWJlciBvZiB0aGUgdGlsZSB3ZSBhcmUgY3VyaW91cyBhYm91dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgc2luZ2xlIGxpbmUgd2l0aCBvbmUgaW50ZWdlciwgc3BlY2lmeWluZyB0aGUgcmVzb3VyY2Ugb2YgdGhlIG50aCB0aWxlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==