Description

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

Input Format

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

Output Format

输出共$n$行，对于每组 $a_i,b_i$，求出一组满足条件的 $x_i,y_i$，每组结果占一行。
本题答案不唯一，输出任意满足条件的$x_i,y_i$均可。

2
4 6
8 18

-1 1
-2 1

Hint

$1≤n≤10^5$,
$1≤a_i,p_i≤2∗10^9$

Source

2.4数学知识 扩展欧几里得算法