"""
算法作用:
欧几里得算法中,根据裴蜀定理,对于任意两个正整数a,b,一定存在整数x,y,使得ax+by = (a,b),其中(a,b)表示a和b的最大公约数
扩展欧几里得算法就是用来求上式的一组系数x,y
即,求x, y,使得ax + by = gcd(a, b)
算法原理:
在欧几里得算法模板上进行修改:
当b==0时,x = 1,y = 0;
当b!=0时,x不变,y = y-(a//b)*x
"""
def exgcd(a, b):
global x, y
if b==0:
x = 1; y = 0 # 当b==0时,x = 1,y = 0;
return a
else:
d = int(exgcd(b, a % b))
# 颠倒x和y的顺序, tmp存x,x存y
tmp = x
x = y
y = tmp-(a//b)*y # y = y-(a//b)*x, 更新y时,更新公式里的y对应x(tmp),x对应y
return d
if __name__=="__main__":
n = int(input().strip())
for _ in range(n):
a, b = map(int, input().split())
# 初始化系数x,y
x = 0
y = 0
exgcd(a, b)
print(x, y)