记录编号	77546	评测结果	AAAAAAAAAA
题目名称	drei	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2013-11-02 08:51:37	内存使用	0.35 MiB

#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream fi("drei.in");
ofstream fo("drei.out");
long long A,P;
bool prime[40001];
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int euler_phi(int n)
{
  int m=(int)sqrt(n+0.5);
  int ans=n;
  for(int 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;
}
long long quickpow(int x)
{
	if(x==1)return A%P;
	long long temp=quickpow(x/2);
	temp=(temp*temp)%P;
	if(x%2==1)temp=(temp*A)%P;
	return temp%P;
}
void work()
{
	fi>>A>>P;
	if(gcd(A,P)!=1||P==1)
	{
		fo<<"-1"<<endl;
		return;
	}
	long long lim=euler_phi(P);
	long long ans=lim;
	for(long long i=2;i<=(long long)sqrt((double)lim+0.5);i++)
	if(ans%i==0)
	{
		long long ta=i,tb=ans/i;
		while(tb%i==0)tb/=i,ta*=i;
		if(quickpow(ta)==1)
		{
			while(quickpow(ta/i)==1)ta/=i;
			ans=min(ta,ans);
		}
		tb=ans;
		while(tb%i==0&&quickpow(tb/i)==1)tb/=i;
		ans=min(tb,ans);
	}
	fo<<ans<<endl;
}
int main()
{
	int T;
	fi>>T;
	while(T--)work();
	return 0;
}