RT

#include<bits/stdc++.h>
using namespace std;
struct IO_Tp {
    const static int _I_Buffer_Size = 2 << 22;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;

    const static int _O_Buffer_Size = 2 << 22;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    IO_Tp() { fread(_I_Buffer, 1, _I_Buffer_Size, stdin); }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(int &res) {
    	int f=1;
        while (!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
        if(*_I_pos=='-')f=-1,++_I_pos;
        res = *_I_pos++ - '0';
        while (isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
        res*=f;
        return *this;
    }

    IO_Tp &operator<<(int n) {
    	if(n<0)*_O_pos++='-',n=-n;
        static char _buf[10];
        char *_pos = _buf;
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf) *_O_pos++ = *--_pos;
        return *this;
    }

    IO_Tp &operator<<(char ch) {
        *_O_pos++ = ch;
        return *this;
    }
} IO;
const int N=1e8+5,S=1e4;
int T,n,m,ans,tot,pr[N],pi[N];
bool vst[N];
int qpow(int a,int b){
	int ret=1;
	while(b){
		if(b&1)ret=1LL*ret*a%m;
		a=1LL*a*a%m;
		b>>=1;
	}
	return ret;
}
void prep(int n){
	for(int i=2;i<=n;++i){
		if(!vst[i])pr[++tot]=i;
		for(int j=1;j<=tot&&1LL*i*pr[j]<=n;++j){
			vst[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	for(int i=1;i<=n;++i)pi[i]=pi[i-1]+(!vst[i]);
}
int main(){
	prep(1e8);
	for(IO>>T;T--;){
		IO>>n>>m;ans=1;
		for(int i=1;i<=tot;++i)if(pr[i]<=S){
			int x=0,t=n;
			while(t)t/=pr[i],x+=t;
			ans=1LL*ans*(x+1)%m;
		}
		for(int l=S+1,r;l<=n;l=r+1){
			r=n/(n/l);
			ans=1LL*ans*qpow(n/l+1,pi[r]-pi[l-1])%m;
		}
		IO<<ans<<'\n';
	}
	return 0;
}