#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<' '<<x<<endl
#ifndef ONLINE_JUDGE
	#define pia getchar
#else
	#define pia nc
#endif
char nc(){
  	static char buf[1<<25],*p=buf,*q=buf;
  	if(p==q&&(q=(p=buf)+fread(buf,1,1<<25,stdin),p==q))return EOF;
  	return *p++;
}
template<class T>void rd(T&x){
	short f=1;x=0;
	char ch=pia();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=pia();
	}while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=pia();
	}x*=f;
}
template<class T>void wr(T x){
	if(x<0)putchar('-'),x=-x;
	if(x>=10)wr(x/10);
	putchar(x%10+48);
}
#define int __int128
#define maxn 640010
int Q[10000][2],T;
int pri[maxn],lpf[maxn],pcnt;
void shai(int n){
	for(int i=2;i<=n;i++){
		if(lpf[i]==0)pri[lpf[i]=++pcnt]=i;
		for(int j=1;j<=lpf[i]&&i*pri[j]<=n;j++)lpf[i*pri[j]]=j;
	}
}
int N,LIM,mx;
#define id(x) ((x)<=LIM?le[x]:ge[N/(x)])
int le[maxn],ge[maxn];
int li[maxn],tot;
int G[maxn];
void init(int N){
	tot=0;
	for(int i=1,j;i<=N;i=N/j+1){
		j=N/i;
		li[++tot]=j;
		id(j)=tot;
		G[tot]=j-1;
	}
}
void calcFprime(){
	for(int k=1;k<=pcnt&&pri[k]*pri[k]<=N;k++)
	for(int i=1;li[i]>=pri[k]*pri[k];i++){
		int d=id(li[i]/pri[k]);
		G[i]-=G[d]-k+1;
	}
}
int ksm(int a,int b,const int& p){
	int ans=1;
	for(;b;b>>=1,a=a*a%p)
	if(b&1)ans=ans*a%p;
	return ans;
}
int S(int l,int r){
	return G[id(r)]-G[id(l-1)];
}
signed main(){
#ifndef ONLINE_JUDGE
	freopen("testdata.in","r",stdin);
#endif
	rd(T);
	for(int i=0;i<T;i++)rd(Q[i][0]),rd(Q[i][1]),mx=max(mx,Q[i][0]);
	shai(int(sqrt((long long)mx)+1000));
	for(int gg=0;gg<T;gg++){
		N=Q[gg][0];
		const int p=Q[gg][1];
		LIM=sqrt((long long)N);
		init(N);
		calcFprime();
		int ans=1;
		for(int i=1;pri[i]<=LIM;i++){
			int u=N,t=0;
			while(u)u/=pri[i],t+=u;
			ans=ans*(t+1)%p;
		}
		for(int L=LIM+1,R;L<=N;L=R+1){
			R=N/(N/L);
			ans=ans*ksm(N/L+1,S(L,R),p)%p;
		}
		wr(ans);putchar('\n');
	}
#ifndef ONLINE_JUDGE
	printf("\n%.2lf",(double)clock()/CLOCKS_PER_SEC);
#endif
}