18940번 - 숫자 카드 제거 게임

Yuto와 Platina가 숫자 카드 게임을 하려고 한다. 이 게임은 처음에 1부터 N까지의 수가 하나씩 적혀 있는 N개의 숫자 카드를 놓고 시작한다.

각 플레이어는 자신의 차례에 숫자 카드 하나를 집는다. 그 카드에 적힌 수가 x라고 할 때, x-1, x, x+1 중 하나가 적혀 있는 모든 숫자 카드를 제거한다.

게임은 번갈아가면서 진행되며 항상 Yuto부터 게임을 시작한다. 자신의 차례를 시작할 때, 남아있는 숫자카드가 없으면 패배한다.

둘은 완벽하게 게임을 진행한다. 둘은 이 게임도 너무나도 재미있는 나머지 숫자카드의 수를 바꾸면서 이 게임도 T판을 진행하려고 한다.

돌돌이는 이 게임이 너무 오래 걸릴 것 같아 보는 게 지겨운 나머지, 미리 결과를 예측하려고 한다.

T판의 각 게임에 대해서 N이 주어졌을 때, 승자를 알려줘서, 돌돌이가 편하게 잘 수 있도록 도와주자!

첫째 줄에 플레이할 게임의 횟수인 양의 정수 T가 주어진다.

이후 T개의 줄에는 각 줄에 게임에서 사용할 숫자카드의 갯수 N이 주어진다.

T개의 줄에 걸쳐서 각 줄마다 이기게 될 사람의 이름을 출력한다.

• 1 ≤ T ≤ 10⁵
• 1 ≤ N ≤ 5×10⁶