시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 5 4 100.000%

문제

모든 자연수 N은 (2a)(3b)의 합으로 나타낼 수 있다. 이 때, 모든 항은 서로소 이어야 한다.

1 = (20)(30)

6 = (22)(30) + (20)(31)

31 = (24)(30) + (20)(32) + (21)(31) = (22)(30) + (20)(33)

N이 주어졌을 때, 이를 (2a)(3b)의 합으로 나타내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 정수 N이 주어진다. (1 <= N < 231)

출력

각 테스트 케이스에 대해 첫째 줄에는 항의 개수 M을 출력한다. 그다음 M개의 줄에 걸쳐 합을 구성하는 항을 출력한다. 어떤 항이 (2a)(3b)일때, a b를 공백으로 구분하여 출력하면 된다.

예제 입력

6
1
7
31
7776
531441
123456789

예제 출력

1
0 0
2
2 0
0 1
3
4 0
0 2
1 1
1
5 5
1
0 12
8
3 13
4 12
2 15
7 8
9 6
0 16
10 5
15 2

힌트