F. Toilet Orders
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas is browsing his favorite catalog of toilet parts and is eager to order toilet bowls and toilet lids for his company, Thomas Crapper And Co in London. Together, one toilet bowl and one toilet lid make one toilet. The catalog knows that Thomas can potentially order many parts so they list their total supply in print. Specifically, Thomas knows that the catalog has $$$b$$$ bowls and $$$l$$$ lids. Due to complex supply and demand economics, Thomas has determined that it is most profitable for him to manufacture exactly $$$g$$$ new toilets, where $$$g$$$ is the greatest common divisor of $$$b$$$ and $$$l$$$. So, he will buy $$$g$$$ new bowls and $$$g$$$ new lids (which together make $$$g$$$ new toilets). For accounting purposes, Thomas wants to record how many new toilets $$$g$$$ were made by listing the prime factors of $$$g$$$ (in increasing order), along with their multiplicities (how many times a prime factor $$$p$$$ evenly divides $$$g$$$). Can you help Thomas?

Input

The first line of input will contain $$$T$$$ $$$(1 \leq T \leq 100)$$$, the number of test cases to follow. The next $$$T$$$ lines of input will contain $$$b$$$ $$$(2 \leq b \leq 10^{12})$$$ bowls and $$$l$$$ $$$(2 \leq l \leq 10^{12})$$$ separated by a single space.

Output

For each test case, output a list of the $$$k$$$ distinct prime factors (along with their multiplicities) of $$$g$$$ in increasing order, where $$$g$$$ is the total number of new toilets that Thomas will make. Note that if $$$g = 1$$$ then no prime factors should be outputted. Among each test case, the $$$i$$$-th line of output should contain the $$$i$$$-th smallest distinct prime factor $$$p_i$$$ of $$$g$$$, followed by a single space, followed by the multiplicity of $$$p_i$$$ in $$$g$$$. End every test case by printing a "0". And repeat for all test cases.

Examples
Input
1
360 240
Output
2 3
3 1
5 1
0
Input
2
83 24
15 25
Output
0
5 1
0
Note

For the first sample test case, see how the greatest common divisor of $$$360$$$ and $$$240$$$ is $$$120 = 2^3 * 3 * 5$$$.

For the second sample test case, see how the gcd of 83 and 24 is 1, and hence no prime factors were printed. The gcd of 15 and 25 is 5, and 5 is prime and has multiplicity one in 5.

IMPORTANT TIP: IF WRITING IN PYTHON AND YOU GET TIME LIMIT EXCEEDED, REMEMBER TO SELECT PYPY WHILE SUBMITTING