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

• 삼각 분할의 갯수가 카탈란수라는 것은 사실 이 문제를 푸는데에는 전혀 관계 없다.
• 볼록다각형을 삼각분할할때 대각선의 갯수가 n-3개. 그래서 이 문제에서 점이 n개일때 그려지게 될 선분의 갯수는 선분을 그리는 방법에 관계 없이 항상 2n-3개라는 것만 알면 충분하다.
• n=0 또는 n=1일때는 그릴수 있는 선분이 0개이므로 출력해야 할 값은 '1 0'이 된다.
• 나머지 경우는 선분의 갯수가 2n-3이므로 항상 홀수개이다. 홀수개일때 번갈아서 선분을 하나씩 그리면 마지막 선분을 선공이 그리게 된다. 그래서 출력해야 할 값은 '0 1'이 된다.
• 결국 모든 케이스에 대해서 n이 2이상인지 여부만 체크하면 된다.

"""Solution code for "BOJ 27296. 카탈란 마스터의 선분 그리기 게임".

- Problem link: https://www.acmicpc.net/problem/27296
- Solution link: http://www.teferi.net/ps/problems/boj/27296

Tags: [game theory]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        print('1 0' if N <= 1 else '0 1')


if __name__ == '__main__':
    main()