Number Theory and Applications

Let us apply number theory. A complex number whose real and imaginary parts are integers is called a Gaussian integer.

\begin{equation*} G=\left{x+yi:::x,y\in\mathbb{Z}\right},\qquad\text{where}\quad i^2=-1 \end{equation*}

The notions of divisor, common divisor, and greatest common divisor carry over from the integers to the Gaussian integers.

• For two Gaussian integers $n,m$, if there is some Gaussian integer $k\in G$ with $m=n\cdot k$, then $n$ is called a divisor of $m$. The relation that $n$ is a divisor of $m$ is written $n\mid m$.
• For two Gaussian integers $n,m$, a Gaussian integer $d$ that is a divisor of both $n$ and $m$ is called a common divisor of $n$ and $m$.
• A common divisor $g$ of two Gaussian integers $n,m$ is called a greatest common divisor if $d\mid g$ holds for every other common divisor $d$.

Given two Gaussian integers, write a program that finds all of their greatest common divisors.

The first line gives the number of test cases $T$. There are at most 1,000 test cases.

From the second line through the $(T+1)$-th line, each line gives one test case. Each test case consists of four integers $a,b,c,d$ between $-10^9$ and $10^9$, separated by spaces. This input corresponds to the Gaussian integers $n=a+bi$ and $m=c+di$. The cases $a=b=0$ and $c=d=0$ are not given.

A Gaussian integer $x+yi$ is printed by printing $x$, a space, and then $y$. For each test case, print the number of greatest common divisors on the first line, and print the greatest common divisors on the second line in lexicographic order. That is, $a+bi$ is printed before $c+di$ when $a<c$, or when $a=c$ and $b<d$.

The greatest common divisor is not unique even among the integers. For example, if an integer $g$ is a greatest common divisor of two integers $n,m$, then $-g$ is also a greatest common divisor of $n,m$.