#include<bits/stdc++.h>
#define mod 1000000007ll
using namespace std;
vector<int> pr;
const double eps=1e-12;
bool vis[10000010]={};
long long sum[10000010]={};
void init()
{
	for(int i=2;i<=10000000;i++)
	{
		if(vis[i]==0)
		{
			pr.push_back(i);
			for(int j=2*i;j<=10000000;j+=i)
			{
				vis[j]=1;
			}
		}
	}
	sum[0]=pr[0];
	for(int i=1;i<pr.size();i++)
	{
		sum[i]=pr[i];
		sum[i]*=sum[i-1];
		sum[i]%=mod;
	}
	
}
long long exgcd(long long a,long long b,long long &x,long long &y){
	long long t,ret;
	if(!b){
		x=1;
		y=0;
		return a;
	}
	ret=exgcd(b,a%b,x,y);
	t=x;
	x=y;
	y=t-a/b*y;
	return ret;
}
int ff(int t)
{
	if(pr[0]>t) return -1;
	int l=0;
	int r=pr.size()-1;
	while(l<r)
	{
		int mid=(l+r)/2+1;
		if(pr[mid]>t) r=mid-1;
		else l=mid;
	}
	return l;
}
int tot=0;
void work()
{
	tot++;
	long long o;
	scanf("%lld",&o);
	long long ans=1;
	int p=3;
	int a,b;
	long long qq;
	while(1)
	{
		long long x=0,y=0;
		int aa=pow(o,1.0/p);
		while(pow(aa+1,p)<=o) aa++;
		a=ff(aa);
		aa=pow(o,1.0/(p-1));
		while(pow(aa+1,p-1)<=o) aa++;
		b=ff(aa);
		if(a==-1&&b==-1) break;
		if(a==-1) qq=sum[b];
		else {x=0; y=0; exgcd(sum[a],mod,x,y); x=(x%mod+mod)%mod; qq=sum[b]*x;}
		qq%=mod;
		for(int i=1;i<=p-2;i++)
		{
			ans*=qq;
			ans%=mod;
		}
		p++;
	}
	printf("Case %d: %lld\n",tot,ans);	
}
int main()
{
	init();
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}