시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB301483317.553%

문제

경근이는 2차원 배열을 분할 정복하여 푸는 문제 “여왕벌”을 접하고 나서 2차원 배열을 분할 했을 때 배열이 어떻게 나뉘는지에 대해 관심이 생겼다.

배열을 분할하는 과정에서 현재 보고 있는 배열의 크기가 N × M 일 때 경근이는 이 배열을 최대한 크기가 비슷한 네 개의 배열로 나눈다. 정확하게 말하면 N ×M 크기의 배열은 \(\lfloor\)N/2\(\rfloor\) × \(\lfloor\)M/2\(\rfloor\), \(\lceil\)N/2\(\rceil\) × \(\lfloor\)M/2\(\rfloor\), \(\lfloor\)N/2\(\rfloor\) × \(\lceil\)M/2\(\rceil\), \(\lceil\)N/2\(\rceil\) × \(\lceil\)M/2\(\rceil\) 크기의 네 배열로 나눈다. \(\lfloor\)x\(\rfloor\)의 값은 x의 값에서 소수점 이하를 버림한 값이고, \(\lceil\)x\(\rceil\)의 값은 x의 값에서 소수점 이하를 올림한 값이다. 예를 들어 4 × 5 크기의 배열은 2 × 2 크기의 배열 두 개와 2 × 3 크기의 배열 두 개로 나뉘게 될 것이고, 5 × 5 크기의 배열은 2 × 2, 3 × 2, 2 × 3, 3 × 3 크기의 네 배열로 나뉘게 될 것이다.

만약 현재 보고 있는 배열의 N, M 중 단 하나라도 1이 되면 경근이는 분할을 중지하고 특별히 처리한다. 따라서 N × M 크기의 배열은 분할 결과 여러 개의 1 × K 크기의 (혹은 돌려서 K × 1 크기의 배열인데, K가 같으면 같은 종류라고 생각하자) 배열로 나뉘게 된다. N, M 이 주어질 때, N × M 크기의 배열을 분할하는 과정을 모두 끝낸 다음 생기는 1 × K 크기의 배열 종류의 개수와 각 종류에 대한 K 값과 그 개수를 출력하는 프로그램을 작성하라.

입력

첫 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 10,000)가 주어진다. 이후 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스는 처음 배열의 크기 N, M (1 ≤ N, M ≤ 1018)이 공백 하나로 구분되어 주어진다.

출력

각 테스트 케이스마다 N × M 크기의 배열을 모두 분할한 다음 생기는 1 × K 크기의 배열의 종류의 개수를 출력한다. 이 값을 C 라고 하자.

다음 C 개의 줄에는 각 1 × K 크기의 배열에 대해 K 와 그 개수를 공백 하나로 구분하여 출력한다. 출력되는 K 는 오름차순이어야 하며, 개수는 너무 많을 수 있으므로 1,234,567,891로 나눈 나머지를 출력한다.

두 테스트 케이스 사이에 빈 줄을 출력하면 안 된다. 정확한 출력 형식은 입출력 예시를 참고한다.

예제 입력 1

3
4 4
4 5
5 5

예제 출력 1

1
1 16
2
1 12
2 4
2
1 13
2 6