다음은 N번째 피보나치 수를 재귀로 구하는 C++ 함수다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

fibonacci(3)을 호출하면 호출이 다음처럼 퍼져 나간다.

• fibonacci(3)이 fibonacci(2)와 fibonacci(1)을 호출한다. (fibonacci(1)의 첫 번째 호출)
• fibonacci(2)가 다시 fibonacci(1)과 fibonacci(0)을 호출한다. (fibonacci(1)의 두 번째 호출)
• 두 번째로 호출된 fibonacci(1)이 "1"을 출력하며 1을 반환한다.
• fibonacci(0)이 "0"을 출력하며 0을 반환한다.
• 두 결과를 받은 fibonacci(2)가 1을 반환한다.
• 첫 번째로 호출된 fibonacci(1)이 "1"을 출력하며 1을 반환한다.
• 두 결과를 받은 fibonacci(3)이 2를 반환한다.

결국 1은 2번, 0은 1번 출력된다. N이 주어질 때 fibonacci(N)을 호출하면 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하라. 재귀를 실제로 전부 실행하면 호출 횟수가 기하급수적으로 늘어난다는 점에 주의하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

이어서 테스트 케이스마다 N이 한 줄에 하나씩 주어진다. N은 40 이하의 자연수 또는 0이다.

출력

테스트 케이스별로 0의 출력 횟수와 1의 출력 횟수를 공백으로 구분해 한 줄에 출력한다.

예제 입력 1

3
0
1
3

예제 출력 1

1 0
0 1
1 2

예제 입력 2

2
6
22

예제 출력 2

5 8
10946 17711