给定n对正整数ai,bi，对于每对数，求出一组 xi,yi，使其满足ai×xi+bi×yi=gcd(ai,bi)。要求xi是最小的非负整数。对于该题只输出xi的值即可。

第一行包含整数 n。

接下来n行，每行包含两个整数 ai,bi。

1≤n≤10^5

1≤ai,bi≤2×10^9