高斯整数的最大公约数 (Gcd of Gaussian Integers)

时间限制：5 秒

题目描述

在本题中，$i$ 表示虚数单位。

给定高斯整数 $a_1 + b_1 i$ 和 $a_2 + b_2 i$，求出它们的最大公约数之一。

关于高斯整数及其最大公约数的定义，请参考以下内容：

• $\mathbb{Z}[i] = \{a + bi \mid a, b \in \mathbb{Z}\}$ 中的元素称为高斯整数。

• 对于 $x, y \in \mathbb{Z}[i]$，若存在 $z \in \mathbb{Z}[i]$ 使得 $y = xz$，则定义 $x \mid y$。

• 高斯整数 $g$ 是 $x, y \in \mathbb{Z}[i]$ 的最大公约数，当且仅当对于 $\mathbb{Z}[i]$ 中的任意 $z$，条件 $z \mid g$ 等价于 $z \mid x$ 且 $z \mid y$。这样的 $g$ 在相差 $\pm 1$ 和 $\pm i$ 的倍意义下是唯一确定的。

你需要解决 $T$ 组测试数据。

约束条件

• $1 \le T \le 10^5$
• $-1 \times 10^9 \le a_1, b_1, a_2, b_2 \le 10^9$

输入

T
a_1 b_1 a_2 b_2
⋮
a_1 b_1 a_2 b_2

输出

当 $a + bi$ 是 $a_1 + b_1 i$ 和 $a_2 + b_2 i$ 的最大公约数时，输出 $a$ 和 $b$。

a b

样例

#1

输入：

8
8 0 6 0
0 0 0 0
0 0 4 8
4 0 6 2
1 2 3 4
1 -2 3 4
1 -3 5 -7
-344235 225420 -33882 162741

输出：

2 0
0 0
4 8
-2 -2
1 0
1 -2
-1 1
-456 123

对于第一组测试数据，除了 2 0 之外，以下答案也是正确的：-2 0、0 2、0 -2。

8
8 0 6 0
0 0 0 0
0 0 4 8
4 0 6 2
1 2 3 4
1 -2 3 4
1 -3 5 -7
-344235 225420 -33882 162741

2 0
0 0
4 8
-2 -2
1 0
1 -2
-1 1
-456 123