#include<bits/stdc++.h>

using namespace std;

long long fi[100099];

long long ff(long long k, long long n, long long m){
    if(n == 0)
        return k%m;
    else if(n == 1)
        return (k*k)%m;
    else if(fi[n] != -1)
        return fi[n];
    else
        return fi[n] = (ff(k, n - 1, m)*ff(k, n - 2, m))%m;
}

int main(){
    long long n, k, m, as;
    int t, tc;
    cin >> tc;
    for(t = 1; t <= tc; t++){
        memset(fi, -1LL, sizeof(fi));
        cin >> n >> k >> m;
        as = ff(k, n, m);
        printf("Case %d: %lld\n", t, as);
    }
    return 0;
}