记录编号	74935	评测结果	AAAAAAAAAA
题目名称	1428.drei	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2013-10-26 18:55:12	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define INF 0x7fffffff
vector<int> prime;
void getprime(void){
	int l[40001]={0};
	int i,j;
	for(i=2;i<=40000;i++){
		if(!l[i]){
			prime.push_back(i);
			for(j=i*i;j<=40000;j+=i) l[j]=true;
		}
	}
}
ll quickpow(ll a,ll x,ll P){//a^x mod P
	ll s=1;
	while(x){
		if(x&1) s=(s*a)%P;
		a=(a*a)%P;
		x>>=1;
	}
	return s;
}
ll ord(ll m,ll a){//使得a^x=1(mod m)的最小x,其中m是素数
	ll i;
	ll ans=INF;
	ll high=sqrt((double)m-1);
	for(i=1;i<=high;i++){
		if((m-1)%i==0){
			if(quickpow(a,i,m)==1) ans=min(ans,i);
			if(quickpow(a,(m-1)/i,m)==1) ans=min(ans,(m-1)/i);
		}
	}
	return ans;
}
ll ord(ll m,ll mk,ll a){//使得a^x=1(mod mk)的最小x,其中m是素数,mk是m的幂
	ll astep=ord(m,a);
	ll tstep=quickpow(a,astep,mk);
	ll ans=astep;
	ll temp=tstep;
	while(temp!=1){
		ans+=astep;
		temp*=tstep;temp%=mk;
	};
	return ans;
}
ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
	return a*b/gcd(a,b);
}
void work(){
	ll a,p;
	scanf("%lld%lld",&a,&p);
	if(gcd(a,p)!=1||p==1){
		printf("-1\n");
		return;
	}
	ll i,j;
	ll ans=1;
	ll temp,temk;
	for(i=0;i<prime.size();i++){
		if(prime[i]>p) break;
		temp=1;temk=0;
		while(p%prime[i]==0){
			temk++,temp*=prime[i];
			p/=prime[i];
		}
		if(temk){
			ans=lcm(ans,ord(prime[i],temp,a));
		}
	}
	if(p>1) ans=lcm(ans,ord(p,a));
	printf("%lld\n",ans);
}
int main(){
	freopen("drei.in","r",stdin);
	freopen("drei.out","w",stdout);
	getprime();
	ll T;
	scanf("%lld",&T);
	for(ll i=1;i<=T;i++) work();
	return 0;
}