#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9-401,N=1e4+5,p[5]={0,2,13,5281,7283},M=1e9-402;
ll qp(ll x,ll y,ll P)
{
	ll res=1;
	while(y)
	{
		if(y&1) (res*=x)%=P;
		(x*=x)%=P,y>>=1;
	}
	return res;
}
void exgcd(ll a,ll b,ll &x,ll &y){
	ll t;
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,x,y);
	t=x,x=y,y=t-a/b*y;
}
ll inv(ll a,ll P)
{
	ll x,y;
	exgcd(a,P,x,y);
	return (x+P)%P;
}
ll g(ll i,ll P){return (i<P)?0:(g(i/P,P)+i/P);}
ll n,m,ans[5],fac[N],res;
ll S(ll now, ll P)
{
	if(now<P) return fac[now]%P;
	ll res=1;
	for(ll i=(now/P)*P+1;i<=now;i++) (res*=i)%=P;
	return qp(fac[P-1]%P,now/P,P)*S(now/P,P)%P*res%P;
}
ll solve(ll now,ll d,ll P)
{
	if(g(now,P)-(now/d)*g(d,P)-g(now/d,P)) return 0;
	return S(now,P)*inv(qp(S(d,P),now/d,P),P)%P*inv(S(now/d,P),P)%P;
}
inline ll rd()
{
	char c;ll f=1;
	while(!isdigit(c=getchar())) if(c=='-')f=-1;
	ll x=c-'0';
	while(isdigit(c=getchar())) x=x*10+(c^48);
	return x*f;
}
int main()
{
	fac[0]=1;
	for(int i=1;i<p[4];i++) fac[i]=fac[i-1]*i%M;
	for(int T=rd();T--;)
	{
		n=rd(),m=rd(),res=0;
		for(int i=1;i<=4;i++)
		{
			ans[i]=0;
			for(ll d=1;d*d<=n;d++) if(n%d==0)
			{
				(ans[i]+=solve(n,d,p[i]))%=p[i];
				if(d*d!=n) (ans[i]+=solve(n,n/d,p[i]))%=p[i];	
			}
		}
		for(int i=1;i<=4;i++)
		{
			ll Mi=M/p[i];
			(res+=ans[i]*Mi%M*inv(Mi,p[i]))%=M;
		}
		cout<<qp(m,res,mod)<<endl;
	}
    return 0; 
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9-401,N=1e4+5,p[5]={0,2,13,5281,7283},M=1e9-402;
ll qp(ll x,ll y,ll P)
{
	ll res=1;
	while(y)
	{
		if(y&1) (res*=x)%=P;
		(x*=x)%=P,y>>=1;
	}
	return res;
}
void exgcd(ll a,ll b,ll &x,ll &y){
	ll t;
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,x,y);
	t=x,x=y,y=t-a/b*y;
}
ll inv(ll a,ll P)
{
	ll x,y;
	exgcd(a,P,x,y);
	return (x+P)%P;
}
ll g(ll i,ll P){return (i<P)?0:(g(i/P,P)+i/P);}
ll n,m,ans[5],fac[N],res;
ll S(ll now, ll P)
{
	if(now<P) return fac[now]%P;
	ll res=1;
	for(ll i=(now/P)*P+1;i<=now;i++) (res*=i)%=P;
	return qp(fac[P-1]%P,now/P,P)*S(now/P,P)%P*res%P;
}
ll solve(ll now,ll d,ll P)
{
	if(g(now,P)-(now/d)*g(d,P)-g(now/d,P)) return 0;
	return S(now,P)*inv(qp(S(d,P),now/d,P),P)%P*inv(S(now/d,P),P)%P;
}
inline ll rd()
{
	char c;ll f=1;
	while(!isdigit(c=getchar())) if(c=='-')f=-1;
	ll x=c-'0';
	while(isdigit(c=getchar())) x=x*10+(c^48);
	return x*f;
}
int main()
{
	fac[0]=1;
	for(int i=1;i<p[4];i++) fac[i]=fac[i-1]*i%M;
	for(int T=rd();T--;)
	{
		n=rd(),m=rd(),res=0;
		for(int i=1;i<=4;i++)
		{
			ans[i]=0;
			for(ll d=1;d*d<=n;d++) if(n%d==0)
			{
				(ans[i]+=solve(n,d,p[i]))%=p[i];
				if(d*d!=n) (ans[i]+=solve(n,n/d,p[i]))%=p[i];	
			}
		}
		for(int i=1;i<=4;i++)
		{
			ll Mi=M/p[i];
			(res+=ans[i]*Mi%M*inv(Mi,p[i]))%=M;
		}
		cout<<qp(m,res,mod)<<endl;
	}
    return 0; 
}