정수론과 응용

정수론을 응용하자. 실수부와 허수부가 정수인 복소수를 가우시안 수라고 한다.

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

가우시안 수에서는 정수의 약수, 공약수, 최대공약수 개념을 그대로 확장할 수 있다.

• 두 가우시안 수 $n,m$에 대해 어떤 가우시안 수 $k\in G$가 존재해 $m=n\cdot k$를 만족할 때, $n$을 $m$의 약수라고 한다. $n$이 $m$의 약수라는 관계를 $n\mid m$으로 적는다.
• 두 가우시안 수 $n,m$에 대해, 가우시안 수 $d$가 $n$의 약수이자 $m$의 약수일 때, $d$를 $n$과 $m$의 공약수라고 한다.
• 두 가우시안 수 $n,m$의 공약수 $g$가 다른 모든 공약수 $d$에 대해 $d\mid g$를 만족할 때, $g$를 최대공약수라고 한다.

두 가우시안 수가 주어졌을 때, 두 수의 모든 최대공약수를 구하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 테스트 케이스는 최대 1,000개 주어진다.

둘째 줄부터 $(T+1)$번째 줄에 걸쳐 각 줄마다 하나의 테스트 케이스가 주어진다. 각 테스트 케이스는 $-10^9$ 이상, $10^9$ 이하인 4개의 정수 $a,b,c,d$가 공백으로 구분해 주어진다. 이 입력은 가우시안 수 $n=a+bi$, $m=c+di$에 해당한다. $a=b=0$ 혹은 $c=d=0$인 경우는 주어지지 않는다.

가우시안 수 $x+yi$는 $x$를 출력하고 공백을 두고 $y$를 출력하는 방식으로 출력한다. 각 테스트 케이스마다 첫 줄에는 최대공약수의 수를 출력하고, 두 번째 줄에는 최대공약수들을 lexicographic order으로 출력한다. 즉, $a<c$ 혹은 $a=c$와 $b<d$일 때, $a+bi$를 $c+di$보다 먼저 출력한다.

최대공약수는 정수에서도 유일하지 않다. 예를 들어 정수 $g$가 두 정수 $n,m$의 최대공약수라면, $-g$도 $n,m$의 최대공약수이다.