记录编号	77507	评测结果	AAAAAAAAAA
题目名称	drei	最终得分	100
用户昵称	zjmfrank2012	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2013-11-01 23:50:00	内存使用	0.32 MiB

#include<fstream>
#include<cmath>
using namespace std;
ifstream fi("drei.in");
ofstream fo("drei.out");
int n,p;
long long pow(int x)
{
	if(x==0)return 1;
	if(x==1)return n%p;
	if(x%2==0)return (pow(x/2)*pow(x/2))%p;
	if(x%2==1)return (((pow(x/2)*pow(x/2))%p)*n)%p;
}
int gcd(int x,int y)
{
	if(x%y==0)return y;
	return gcd(y,x%y);
}
int phi(int x)
{
	int i;
	bool b;
	long long s=x;
	while(x!=1)
	{
		b=0;
		for(i=2;i<=sqrt(x+0.5);i++)
		{	
			if(x%i==0)
			{
				s*=(i-1);
				s/=i;
				b=1;
				while(x%i==0)
				{
					x/=i;
				}
				break;
			}
		}
		if(!b)
		{
			s*=(x-1);
			s/=x;
			return s;
		}
	}
	return (int)s;
}
int jie(int x)
{
	int i,t=-1;
	for(i=1;i<=sqrt(x+0.5);i++)
	{
		if(x%i==0)
		{
			if(pow(i)%p==1)
			{	
				return i;
			}
			if(pow(x/i)%p==1)
			{
				if(t==-1)t=x/i;
				else t=min(t,x/i);
			}
		}
	}
	if(t!=-1)return t;
}
int main()
{
	int m,i;
	fi>>m;
	for(i=1;i<=m;i++)
	{
		fi>>n>>p;
		if(gcd(n,p)!=1||p==1)
		{
			fo<<"-1"<<endl;
		}
		else
		{
			fo<<jie(phi(p))<<endl;
		}
	}
	return 0;
}