扩展欧几里得

题目描述

输入$T$，一共$T$组数据，每组两个数$a, b$，输出$ax-by=\gcd(a,b)$的最小非负整数解$(x, y)$。

输入格式

第一行一个数字$T$。

接下来$T$行，每行两个数字$a, b$。

输出格式

一共$T$行，每行两个数，表示$x, y$。

样例输入

2
1 2
100 150

样例输出

1 0
2 1

数据范围

对于$100\%$的数据，保证$1\leq T\leq 10^4, 1\leq a, b\leq 10^9$。