C++ :

#include<bits/stdc++.h>
using namespace std;
long long t,a,p;
long long ys[100010];
long long fpow(long long a,long long b,long long mod)
{
	if(b==0) return 1;
	if(b==1) return a%mod;
	if(b&1)  return a*fpow(a*a%mod,b>>1,mod)%mod;
	else return fpow(a*a%mod,b>>1,mod)%mod;
}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>a>>p;
		if(fpow(a,p-1,p)!=1)printf("No\n");
		else
		{
			int f=0,t=0;
			//找除了1和本身以外的其它因数，存起来
			for(int i=2;i*i<=p-1;i++)
			{
				if((p-1)%i==0)
				{
					ys[++t]=i;
					ys[++t]=(p-1)/i;
				}
			}
			for(int i=1;i<=t;i++)
			{
				if(fpow(a,ys[i],p)==1)
				{
					printf("No\n");
					f=1;
					break;
				}
			}
			if(f==0)
			{
				printf("Yes\n");
			}
		}
	}
	return 0;
}