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

고려대학교 사이버국방학과 동아리 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}$)이 하나씩 주어진다.

각 테스트케이스마다 한 줄에 두 수를 공백으로 구분해 출력한다. 첫 번째 수는 $P = 0$일 때의 결과이고, 두 번째 수는 $P = 1$일 때의 결과이다. 선공이 이기면 0, 후공이 이기면 1을 출력한다.