#include<bits/stdc++.h>
using namespace std;
const long long int N=1000010;
long long t,a,n,p,hold,phi[N];
int temp[N];
long long power(long long a,long long b)
{
long long res=1;
while(b)
{
if(b&1)
{
res=(res*1LL*a)%p;
}
a=(a*a)%p;
b>>=1;
}
return res;
}
void sieve()
{
phi[1]=1;
for(long long int i=2;i<N;i++)
{
if(phi[i]!=0)continue;
phi[i]=i-1;
for(long long j=2*i;j<N;j+=i)
{
if(!phi[j])
phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
}
int main(int argc, char const *argv[])
{
scanf("%lld",&t);
sieve();
for(int tt=1;tt<=t;tt++)
{
scanf("%lld%lld%lld",&a,&n,&p);
memset(temp,-1,sizeof(temp));
if(__gcd(a,p)==1)
{
hold=1;
for(int i=1;i<=n;i++)
{
hold=(hold*i)%(phi[p]);
}
cout<<"Case #"<<tt<<": "<<power((long long)a,hold)%p<<"\n";
}
else
{
temp[1]=0;
int x,c;
long long mul=1;
for(int i=1;;i++)
{
if(temp[mul*a%p]!=-1)
{
x=temp[mul*a%p];
c=temp[mul]+1-x;
break;
}
else
{
temp[mul*a%p]=temp[mul]+1;
mul=mul*a%p;
}
}
hold=1;
//cout<<"x= "<<x<<" c= "<<c<<endl;
for(int i=1;i<=n;i++)
{
hold=(hold*i)%(c);
}
hold=(hold-x+c)%c;
while(hold<0)
hold+=c;
hold%=c;
cout<<"Case #"<<tt<<": "<<(power((long long)a,hold)%p*power(a,x)%p)%p<<"\n";
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgbG9uZyBsb25nIGludCBOPTEwMDAwMTA7CmxvbmcgbG9uZyB0LGEsbixwLGhvbGQscGhpW05dOwppbnQgdGVtcFtOXTsKbG9uZyBsb25nIHBvd2VyKGxvbmcgbG9uZyBhLGxvbmcgbG9uZyBiKQp7Cglsb25nIGxvbmcgcmVzPTE7Cgl3aGlsZShiKQoJewoJCWlmKGImMSkKCQl7CgkJCXJlcz0ocmVzKjFMTCphKSVwOwoJCX0KCQlhPShhKmEpJXA7CgkJYj4+PTE7Cgl9CglyZXR1cm4gcmVzOwp9CnZvaWQgc2lldmUoKQp7CiAgICBwaGlbMV09MTsKICAgIGZvcihsb25nIGxvbmcgaW50IGk9MjtpPE47aSsrKQogICAgewogICAgICAgIGlmKHBoaVtpXSE9MCljb250aW51ZTsKICAgICAgICBwaGlbaV09aS0xOwogICAgICAgIGZvcihsb25nIGxvbmcgaj0yKmk7ajxOO2orPWkpCiAgICAgICAgewogICAgICAgICAgICBpZighcGhpW2pdKQogICAgICAgICAgICAgICAgcGhpW2pdPWo7CiAgICAgICAgICAgIHBoaVtqXT1waGlbal0vaSooaS0xKTsKICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgY29uc3QgKmFyZ3ZbXSkKewoJc2NhbmYoIiVsbGQiLCZ0KTsKCXNpZXZlKCk7Cglmb3IoaW50IHR0PTE7dHQ8PXQ7dHQrKykKCXsKCQlzY2FuZigiJWxsZCVsbGQlbGxkIiwmYSwmbiwmcCk7CgkJbWVtc2V0KHRlbXAsLTEsc2l6ZW9mKHRlbXApKTsKCQlpZihfX2djZChhLHApPT0xKQoJCXsKCQkJaG9sZD0xOwoJCQlmb3IoaW50IGk9MTtpPD1uO2krKykKCQkJewoJCQkJaG9sZD0oaG9sZCppKSUocGhpW3BdKTsKCQkJfQoJCQljb3V0PDwiQ2FzZSAjIjw8dHQ8PCI6ICI8PHBvd2VyKChsb25nIGxvbmcpYSxob2xkKSVwPDwiXG4iOwoJCX0KCQllbHNlCgkJewoJCQl0ZW1wWzFdPTA7CgkJCWludCB4LGM7CgkJCWxvbmcgbG9uZyBtdWw9MTsKCQkJZm9yKGludCBpPTE7O2krKykKCQkJewoJCQkJaWYodGVtcFttdWwqYSVwXSE9LTEpCgkJCQl7CgkJCQkJeD10ZW1wW211bCphJXBdOwoJCQkJCWM9dGVtcFttdWxdKzEteDsKCQkJCQlicmVhazsKCQkJCX0KCQkJCWVsc2UKCQkJCXsKCQkJCQl0ZW1wW211bCphJXBdPXRlbXBbbXVsXSsxOwoJCQkJCW11bD1tdWwqYSVwOwoJCQkJfQoJCQl9CgkJCWhvbGQ9MTsKCQkJLy9jb3V0PDwieD0gIjw8eDw8IiBjPSAiPDxjPDxlbmRsOwoJCQlmb3IoaW50IGk9MTtpPD1uO2krKykKCQkJewoJCQkJaG9sZD0oaG9sZCppKSUoYyk7CgkJCX0KCQkJaG9sZD0oaG9sZC14K2MpJWM7CgkJCXdoaWxlKGhvbGQ8MCkKCQkJCWhvbGQrPWM7CgkJCWhvbGQlPWM7CgkJCWNvdXQ8PCJDYXNlICMiPDx0dDw8IjogIjw8KHBvd2VyKChsb25nIGxvbmcpYSxob2xkKSVwKnBvd2VyKGEseCklcCklcDw8IlxuIjsKCQl9Cgl9CglyZXR1cm4gMDsKfQ==