배열 분할

2차원 배열을 분할 정복으로 처리하면 배열은 점점 작은 조각으로 쪼개진다. 이 문제는 마지막에 남는 조각의 모양과 개수를 센다.

크기가 $N \times M$인 배열은 크기가 최대한 비슷한 네 개의 배열로 나뉜다. 정확히는 $\lfloor N/2 \rfloor \times \lfloor M/2 \rfloor$, $\lceil N/2 \rceil \times \lfloor M/2 \rfloor$, $\lfloor N/2 \rfloor \times \lceil M/2 \rceil$, $\lceil N/2 \rceil \times \lceil M/2 \rceil$ 크기의 네 배열이다. $\lfloor x \rfloor$는 $x$의 소수점 이하를 버린 값이고, $\lceil x \rceil$는 올린 값이다. 예를 들어 $4 \times 5$ 배열은 $2 \times 2$ 배열 두 개와 $2 \times 3$ 배열 두 개로 나뉘고, $5 \times 5$ 배열은 $2 \times 2$, $3 \times 2$, $2 \times 3$, $3 \times 3$ 배열 네 개로 나뉜다.

지금 보고 있는 배열의 두 변 중 하나라도 길이가 1이면 그 배열은 더 나누지 않고 그대로 남긴다. 그래서 분할을 끝까지 진행하면 처음 배열은 여러 개의 $1 \times K$ 배열로 남는다. $K \times 1$ 배열은 돌리면 $1 \times K$ 배열이므로 같은 종류로 센다.

$N$과 $M$이 주어진다. 분할을 모두 끝낸 뒤 남는 $1 \times K$ 배열이 몇 종류인지, 그리고 각 종류의 $K$와 그 개수가 얼마인지 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10\,000$)가 주어진다.

이어지는 $T$개의 줄에 각각 배열의 처음 크기 $N$과 $M$ ($1 \le N, M \le 10^{18}$)이 공백 하나로 구분되어 주어진다.

각 테스트 케이스마다 먼저 분할이 끝난 뒤 남는 $1 \times K$ 배열의 종류 수 $C$를 한 줄에 출력한다.

이어지는 $C$개의 줄에 각 종류의 $K$와 그 종류의 개수를 공백 하나로 구분해 출력한다. $K$는 오름차순으로 출력한다. 개수는 매우 커질 수 있으므로 1,234,567,891로 나눈 나머지를 출력한다. 나머지가 0이 되는 종류도 $C$에 포함하고 그대로 출력한다.

테스트 케이스 사이에 빈 줄을 넣지 않는다.