Shirogane와 Shinomiya는 젠가를 하고 있다.
모든 블록은 크기가 이고 질량이 인 균일한 직육면체이다. 한 층은 서로 평행한 블록 개를 빈틈없이 나란히 놓아 만든다. 서로 이웃한 두 층의 블록 방향은 서로 수직이다. 맨 아래층을 층, 맨 위층을 층이라 한다.
두 사람은 번갈아 가장 위층이 아닌 곳에 남아 있는 블록 하나를 골라 제거한다. 제거한 블록을 다시 쌓지는 않는다.
이 문제에서는 탑이 쓰러지는 조건을 다음과 같이 정의한다. 각 ()에 대하여 다음 두 대상을 생각하자.
어떤 에 대해 가 비어 있거나 가 의 내부 또는 경계에 속하지 않으면 탑이 쓰러진다. 모든 에 대해 이 조건을 만족하면 탑은 쓰러지지 않는다.
블록을 제거한 뒤 탑이 쓰러지면 그 블록을 제거한 사람이 즉시 패배한다. 따라서 자신의 차례에 탑을 쓰러뜨리지 않고 제거할 수 있는 블록이 하나도 없다면 패배한다. 가장 위층인 층의 블록은 제거할 수 없다.
탑의 높이 가 주어진다. 두 사람이 최선의 방법으로 게임할 때 승자를 구하여라. Shirogane가 먼저 시작한다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 Shirogane가 이긴다면 Shirogane를, Shinomiya가 이긴다면 Shinomiya를 한 줄에 출력한다.
각 케이스는 다음과 같은 형식으로 주어진다.
| 3 | 50 | 추가적인 제약이 없다. |
