题目描述

给定n对正整数$a_i$，$b_i$，对于每对数，求出一组$x_i$，$y_i$，使其满足$a_i$×$x_i$+$b_i$×$y_i$=gcd($a_i$，$b_i$)。

输入格式

第一行包含整数n。

接下来n行，每行包含两个整数$a_i$，$b_i$。

输出格式

输出共n行，对于每组$a_i$，$b_i$，求出一组满足条件的$x_i$，$y_i$，每组结果占一行。

2
4 6
8 18

-1 1
-2 1

提示

数据范围

1≤n≤${10}^5$,
1≤$a_i,b_i$≤2×${10}^9$。