#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <math.h>
#include <list>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define For0(i,n) for(int i=0;i<(int)n;i++)
#define For1(i,n) for(int i=1;i<=(int)n;i++)
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
ll mod;
class M{
public:
long long  val[4][4];
    M(){memset(val, 0, sizeof(val));}
    void identity(){ For0(i, 2) val[i][i] = 1;}
    M operator *(M c){
    M ans;
    For0(i, 2) For0(j, 2) For0(k, 2){
    ans.val[i][j] = ((ans.val[i][j])%mod + (val[i][k] * c.val[k][j])%mod)%mod;
    }
    return ans;
    }
}A;
M power(M x, ll p)
{
    if(p==1) return x;
    if(p&1) return x * power(x, p-1);
    M ans = power(x, p/2);
    ans = ans * ans;
    return ans;
}
 
 
ll fibo(ll a,ll b,ll n)
{
if(n == 1) return b;
A.val[0][0] = A.val[0][1] = A.val[1][0] = 1;
A.val[1][1] = 0;
A = (power(A, n-1));
ll ans = ((A.val[0][0]*b)%mod + (A.val[0][1]*a)%mod)%mod ;
return ans%mod;
}
ll po(ll n,ll k)
{
    if(n==0) return 1%mod;
    ll x = po(n/2,k);
    x  =(x*x)%mod;
    if(n&1) x = (x*k)%mod;
    return x;
}
int main()
{
    ll tc,cas=0;
    scanf("%lld",&tc);
    while(tc--){
ll a,b,k,n,m,res=0;
a = 1;
b = 2;
scanf("%lld %lld %lld",&n,&k,&mod);
if(n==1)
    res=1;
else
 res = fibo(a, b, n);
 
printf("Case %lld: %lld\n",++cas,po(res,k)%mod);
    }
return 0;
}