#include <bits/stdc++.h>
using namespace std;
#define maxn 1000005
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
bool isprime[maxn];
int prime[maxn];
int f[maxn];
int cnt=0;
void PJ(){
    memset(isprime,0,sizeof(isprime));
    cnt=0;
    for(int i=2;i<=1000000;i++){
        if(!isprime[i]){
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&prime[j]*i<=maxn;j++){
            isprime[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}
ll quick_pow(ll x,int y) {
    ll ans = 1;
    while(y) {
        if (y&1)
            ans = (ans*x)%mod;
        x = x*x%mod;
        y >>= 1;
    }
    return ans;
}
int main()
{
    PJ();
    for (int i = 1;i<= 1000000;i++)
        for (int j = 0;j<cnt&&(ll)i*prime[j]<=1000000ll;j++)
            f[i*prime[j]] = f[i]+1;
    int cas;
    scanf("%d",&cas);
    while (cas--) {
        int n,c;
        scanf("%d%d",&n,&c);
        int y = f[n];
        printf("%lld\n",quick_pow(c,y));
    }
    return 0;
}