记录编号	187496	评测结果	AAAAAAAAAA
题目名称	drei	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.147 s
提交时间	2015-09-19 11:00:29	内存使用	0.23 MiB

#define ll long long

#include <cstdio>
#include <cmath>

int t;

ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}

ll Get_Phi(ll n){
    if(n==1){
        return 0;
    }
    ll Ans=n,m=(ll)(sqrt(n+0.5));
    for(ll i=2;i<=m;i++){
        if(n%i==0){
            Ans=Ans/i*(i-1);
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>1){
        Ans=Ans/n*(n-1);
    }
    return Ans;
}

inline ll Pow(ll a,ll b,ll Mod){
	ll Ans=1;
	while(b){
		if(b&1){
			Ans*=a;Ans%=Mod;
		}
		b>>=1;a*=a;a%=Mod;
	}
	return Ans;
}

inline void Work(){
	ll a,b,Gcd,Ans,pr;
	scanf("%lld%lld",&a,&b);Gcd=gcd(a,b);
	if(b==1||Gcd!=1){
		printf("-1");
	}
	else{
		if(a==1){
			printf("1");
		}
		else{
			Ans=Get_Phi(b);
			pr=(ll)sqrt(Ans+0.5);
			for(ll i=1;i<=pr;i++){
				if(Ans%i==0&&Pow(a,i,b)==1){
					printf("%lld",i);return;
				}
			}
			for(ll i=pr;i>=1;i--){
				if(Ans%i==0&&Pow(a,Ans/i,b)==1){
					printf("%lld",Ans/i);return;
				}
			}
		}
	}
	return;
}

int main(){
	freopen("drei.in","r",stdin);
	freopen("drei.out","w",stdout);
	scanf("%d",&t);
	for(int i=0;i<t;i++){
		Work();puts("");
	}
	return 0;
}