Array splitting

Divide and conquer on a two dimensional array keeps cutting the array into smaller pieces. This problem counts the pieces that are left at the end.

An array of size $N \times M$ splits into four arrays whose sizes are as close to each other as possible: $\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$, and $\lceil N/2 \rceil \times \lceil M/2 \rceil$. Here $\lfloor x \rfloor$ is $x$ rounded down and $\lceil x \rceil$ is $x$ rounded up. For example, a $4 \times 5$ array splits into two $2 \times 2$ arrays and two $2 \times 3$ arrays, and a $5 \times 5$ array splits into a $2 \times 2$, a $3 \times 2$, a $2 \times 3$, and a $3 \times 3$ array.

If either side of the array you are looking at has length 1, that array is kept as it is and is never split again. Running the process to the end therefore leaves the original array as a collection of $1 \times K$ arrays. A $K \times 1$ array is a rotated $1 \times K$ array, so the two count as one kind.

Given $N$ and $M$, report how many kinds of $1 \times K$ arrays are left once the splitting is finished, together with $K$ and the count for each kind.

The first line has the number of test cases $T$ ($1 \le T \le 10\,000$).

Each of the next $T$ lines has the starting size of an array, $N$ and $M$ ($1 \le N, M \le 10^{18}$), separated by one space.

For each test case, first print on its own line the number of kinds of $1 \times K$ arrays left after the splitting. Call this value $C$.

Then print $C$ lines, each holding $K$ and the count for that kind separated by one space. Print the values of $K$ in increasing order. A count can be very large, so print it modulo 1,234,567,891. A kind whose count is 0 after the modulo still adds to $C$ and is still printed.

Do not print a blank line between test cases.