说明

给两个正整数$a$和$b$，求出满足$a \ast x + b \ast y = gcd(a, b)$的一组整数解$x$，$y$

已知对于一对正整数$a_{0}$和$b_{0}$，必然存在一组整数解$x_{0}$和$y_{0}$使得$a_{0} \ast x_{0} + b_{0}\ast y_{0} = gcd(a_{0}, b_{0})$，证明略

由欧几里得算法可知，$gcd(a_{0}, b_{0}) = gcd(b_{0}, a_{0} \% b_{0})$

则$a_{0} \ast x_{0} + b_{0} \ast y_{0} = gcd(a_{0}, b_{0}) = gcd(b_{0}, a_{0} \% b_{0}) = b_{0} \ast x_{1} + (a_{0} \% b_{0}) \ast y_{1}$

即存在一对整数$x_{1}$和$y_{1}$，使得 $a_{0} \ast x_{0} + b_{0} \ast y_{0} = b_{0} \ast x_{1} + (a_{0} \% b_{0}) \ast y_{1}$

由于$a_{0} \% b_{0} = a_{0} - (a_{0} / b_{0}) \ast b_{0}$，（这儿的除为向下取整的除法）

则$a_{0} \ast x_{0} + b_{0} \ast y_{0} = b_{0} \ast x_{1} + (a_{0} - (a_{0} / b_{0}) \ast b_{0}) \ast y_{1}$

经过变换可得，$a_{0} \ast x_{0} + b_{0} \ast y_{0} = a_{0} \ast y_{1} + b_{0} \ast (x_{1} - (a_{0} / b_{0}) \ast y_{1})$

所以$x_{0} = y_{1}$，$y_{0} = x_{1} - (a_{0} / b_{0}) \ast y_{1}$

依次类推，$x_{1} = y_{2}$，$y_{1} = x_{2} - (a_{1} / b_{1}) \ast y_{2}$，其中$a_{1} = b_{0}$，$b_{1} = a_{0} \% b_{0}$

$x_{2} = y_{3}$，$y_{2} = x_{3} - (a_{2} / b_{2}) \ast y_{3}$，其中$a_{2} = b_{1}$，$b_{2} = a_{1} \% b_{1}$

...

当$b_{n} = 0$时，就不能再往下进行了，此时$a_{n} \ast x_{n} + b_{n} \ast y_{n} = a_{n} \ast x_{n} = gcd(a_{n}, b_{n}) = a_{n}$

则$x_{n} = 1, y_{n} = 0$

可以看出，“其中”后面的部分就是求GCD的过程，所以我们可以在求GCD的过程中加入一些操作，使得$x_{n}, y_{n}$顺带被求出来

我们把这一修改后的算法称之为EXGCD

输入格式

第一行包含一个正整数$T(1 \leq T \leq 1000)$,表示$T$组数据

随后的$T$行,每行两个正整数$a, b$,含义如上所述$(1 \leq a,b \leq 2^{31} - 1)$。

输出格式

输出包括$T$行，每行两个不小于$-2^{31}$且不大于$2^{31} - 1$的整数，表示$x$和$y$

样例

2
5 6
8 6

-1 1
1 -1