27296번 - 카탈란 마스터의 선분 그리기 게임

문제

고려대학교 사이버국방학과 동아리 MatKor에서 카탈란 수에 대해 배운 예훈이는 이제 카탈란 수에 대해 마스터해 모든 카탈란 수와 관련된 문제를 풀 수 있는 지경에 올랐다고 말했다. 예훈이의 엄청난 실력에 감동한 동우는 MatKor의 다음 세미나 주제인 게임 이론에 이를 반영하기로 했다.

동우가 제안한 게임은 예훈이와 창호 두 명에서 플레이하며, 다음과 같다.

1. 게임이 시작하기 전 동전을 던져 앞면이면 $P = 0,ドル 뒷면이면 $P = 1$로 한다.
2. 원 위에 서로 다른 $N$ (0ドル \le N \le 10^{18}$)개의 점을 찍는다.
3. 플레이어는 자신의 차례에 $N$개의 점 중 두 개의 점을 선택해 선분을 그린다. 단, 이때 이미 그려져 있는 다른 선분과 원 내부에서 교차하면 안 된다.
4. 선분을 그리면 상대 플레이어에게 차례가 넘어간다.
5. 자신의 차례에 더 이상 선분을 그릴 수 없을 경우 $P = 0$이면 패배하고, $P = 1$이면 승리한다.

$P$는 게임이 시작하기 전 동전을 던져 정한 후, 예훈이와 창호에게 모두 알려준다.

예훈이는 이 게임이 끝난 후 가능한 최종 상태의 모양의 개수가 $C_{N-2}$($N-2$번째 카탈란 수)개인 것을 알지만 선분을 먼저 그리는 것이 유리할지 나중에 그리는 것이 유리할지 모른다.

두 명의 플레이어가 모두 자신이 승리하기 위해 최선으로 행동한다면, 선공과 후공 중 누가 이길지 알아내 예훈이에게 알려주자.

입력

첫 번째 줄에 테스트케이스의 개수 $T$ (1ドル \le T \le 10^5$)이 주어진다.

각 테스트케이스 별로 한 줄에 하나씩 점의 개수 $N$ (0ドル \le N \le 10^{18}$)이 주어진다.

출력

각 테스트케이스 별로 한 줄씩 점의 개수가 $N$일때, $P = 0,ドル $P = 1$ 각각에 대해 선공이 이기면 0, 후공이 이기면 1을 공백으로 구분해 출력한다.

제한

힌트