#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#include <cstring>#define LL __int64using namespace std;int fact[1000],fp;bool isprime[35000];int prime[35000],np;void getprime(){	np=0;	memset(isprime,true,sizeof(isprime));	for(int i=2;i<35000;i++){		if(isprime[i]){			prime[np++]=i;			for(int j=i*i;j<35000;j+=i)			isprime[j]=false;		}	}}int Power(int a,int b,int m){	int ans=1; 	a=a%m;	while(b){		if(b&1) ans=(ans*a)%m;		a=(a*a)%m;		b=b>>1;	}	return ans;}int Euler(int s){	int res=s;	for(int i=0;i<np&&prime[i]*prime[i]<=s;i++){		if(s%prime[i]==0){			res=res-res/prime[i];			while(s%prime[i]==0)			s=s/prime[i];		}	}	if(s>1)	res=res-res/s;	return res;}void Burnside(int n,int p){	fp=0;	for(int i=1;i*i<=n;i++){		if(n%i==0){			fact[fp++]=i;			if(n/i!=i)			fact[fp++]=n/i;		}	}	int ans=0;	for(int i=0;i<fp;i++){		ans=(ans+Power(n,fact[i]-1,p)*((Euler(n/fact[i]))%p))%p;  //此处是fact[i]-1表明 除以n，这是因为为了MOD P 	}	ans%=p;	printf("%d\n",ans);}int main(){	getprime();	int T,n,p;	scanf("%d",&T);	while(T--){		scanf("%d%d",&n,&p);		Burnside(n,p);	}	return 0;}