#include<stdio.h>
 
#define MOD 1000000007
 
int prime[1000010]={0};
int f[1000010]={0};
 
void init()
{
	int i; 
    for(i=2;i<=1000005;++i)
	{
        if(!prime[i])
		{
            prime[++prime[0]]=i;
            f[i]=1;
        }
        int j;
        for(j=1;j<=prime[0];j++)
		{
            if(i*prime[j]>1000005)
			{
				break;
			}
            prime[i*prime[j]]=1;
            f[i*prime[j]]=f[i]+1;
            if(i%prime[j]==0)
			{
                break;
            }
        }
    }
    return;
}
 
long long QPow(long long bas,long long t)
{
    long long ret=1;
    for(;t;t>>=1,bas=(bas*bas)%MOD)
    {
        if(t&1LL)
        {
            ret=(ret*bas)%MOD;
        }
    }
    return ret;
}
 
int main()
{
    int t;
    scanf("%d",&t);
    init();
    while(t--)
	{
		long long x,c;
		scanf("%lld%lld",&x,&c);
		long long ans=0;
		long long tmp=QPow(c,(long long)f[x]);
        printf("%lld\n",tmp);
    }
    return 0;
}