已知正整数a和m,若ax mod m为1,则在模m意义下,称x为a的乘法逆元。例如2*3 mod 5为1,则在模5意义下2和3互为乘法逆元。当然在有些情况下不存在乘法逆元,例如模6意义下不存在2的乘法逆元,因为2乘以任何正整数再模6都不可能得到1。对于若干组a和m,求出模m意义下a的乘法逆元。若不存在就用0代替。

输入：输入第一行为正整数T代表共有T组数据,每组数据占一行共2个正整数a和m。T<=1000, 1<=a<=m<=1000000。

样例： 3 4 5 3 7 8 2

输出：4 5 0

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	ll xp,yp;
	ll g=exgcd(b,a%b,xp,yp);
	x=yp;
	y=xp-a/b*yp;
	return g;
}
ll inverse(ll a,ll MOD){
	ll x,y;
	ll g=exgcd(a,MOD,x,y);
	if(g==1)return (x%MOD+MOD)%MOD;
	cout<<0<<endl;
	return -1;
}
int main(){
   ll T;
    cin>>T;
    while(T--){
    ll a1,m;
    	cin>>a1>>m;
    	inverse(a1,m);
	}
    return 0; 
}