记录编号	186597	评测结果	AAAAAAAAAA
题目名称	drei	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.065 s
提交时间	2015-09-13 22:30:43	内存使用	0.31 MiB

#include<cstdio>
#include<iostream>
#include<deque>
#include<cmath>
using namespace std;
typedef long long LL;
const int INF=0x7fffffff;
int a,t,p;
deque<int> prime;
int gcd(int x,int y)
{
	if(y==0)
		return x;
	return gcd(y,x%y);
}
void make_prime()
{
	bool inq[40001];
	for(int i=2;i<=40000;i++)
	{
		if(!inq[i])
		{
			inq[i]=1;
			prime.push_back(i);
			for(int j=i*i;j<=40000;j+=i)
				inq[i]=1;
		}
	}
}
LL quickpow(LL a,LL t,LL mod)
{
	LL re=1;
	while(t)
	{
		if(t&1) re*=a;
		t>>=1;a*=a;re%=mod;a%=mod;
	}
	return re;
}
LL get_mod(LL e,LL m)
{
	LL ans=INF;
	LL high=(LL)sqrt(double(m-1));
	for(LL i=1;i<=high;i++)
	{
		if((m-1)%i!=0) continue;
		if(quickpow(e,i,m)==1) ans=min(ans,i);
		if(quickpow(e,(m-1)/i,m)==1) ans=min(ans,(m-1)/i);
	}
	return ans;
}
LL get(LL e,LL m,LL mk)
{
	LL astep=get_mod(e,m);
	LL sstep=quickpow(e,astep,mk);
	LL ans=astep;
	LL temp=sstep;
	while(temp!=1)
	{
		ans+=astep;
		temp*=sstep;temp%=mk;
	}
	return ans;
}
LL lcm(LL a,LL b)
{
	return a*b/gcd(a,b);
}
void work()
{
	scanf("%d%d",&a,&p);
	if(gcd(a,p)!=1||p==1)
	{
		printf("-1\n");
		return;
	}
	LL ans=1;
	for(int i=0;i<prime.size();i++)
	{
		if(prime[i]>p) break;
		if(p%prime[i]==0)
		{
			LL tem=1;
			//cout<<p<<" "<<prime[i]<<endl;
			while(p%prime[i]==0)
			{
				tem*=prime[i];p/=prime[i];
			}
			ans=lcm(ans,get(a,prime[i],tem));
		}
	}
	if(p>1) ans=lcm(ans,get_mod(a,p));
	printf("%d\n",ans);//lld
	return;
}
int main()
{
	freopen("drei.in","r",stdin);
	freopen("drei.out","w",stdout);
	scanf("%d",&t);
	make_prime();
	for(int i=1;i<=t;i++) work();
	return 0;
}