#include<cstdio>
#define int long long
inline int sqr(int a,int m){return a*a%m;}
int pow(int a,int n,int m)
{
	if(n<1)return 1;
	if(n&1)return sqr(pow(a,n>>1,m),m)*a%m;
	return sqr(pow(a,n>>1,m),m);
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void gcd(int x,int y,int &a,int &b)
{
	if(!y){a=1;b=0;return;}
	gcd(y,x%y,b,a);b-=x/y*a;
}
int solve(int a,int m)
{
	if(m==1)return 1;
	int phi=m,k=m;
	for(int i=2;i*i<=m;i++)
		if(k%i==0)
		{
			phi=phi/i*(i-1);
			while(k%i==0)k/=i;
		}
	if(k>1)phi=phi/k*(k-1);
	int g=gcd(m,phi),y=solve(a,g),o=((pow(a,y,m)-y)%m+m)%m,p,q;
	if(y==-1||o%g)return -1;
	gcd(phi,m,p,q);
	p=(p+m)%m*o/g%m;
	int res=(phi*p+y)%(m*phi);
	if(!res)res=m*phi;
	return res;
}
int q,a,m;
signed main()
{
	scanf("%lld",&q);
	while(q--)
	{
		scanf("%lld%lld",&a,&m);
		printf("%lld\n",solve(a,m));
	}
	return 0;
}