#include "bits/stdc++.h"
using namespace std;
int t;
int a , n , p;
int ans;
int power(int a , int b , int mod){
int res = 1;
while(b){
if(b & 1){
res = (1LL * res * a) % mod;
}
a = (1LL * a * a) % mod;
b >>= 1;
}
return res;
}
int main(){
scanf("%d" , &t);
for(int tc = 1 ; tc <= t ; ++tc){
scanf("%d %d %d" , &a , &n , &p);
ans = a;
for(int i = 1 ; i <= n ; ++i){
ans = power(ans , i , p);
}
printf("Case #%d: %d\n" , tc , ans);
}
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCB0OwppbnQgYSAsIG4gLCBwOwppbnQgYW5zOwppbnQgcG93ZXIoaW50IGEgLCBpbnQgYiAsIGludCBtb2QpewoJaW50IHJlcyA9IDE7Cgl3aGlsZShiKXsKCQlpZihiICYgMSl7CgkJCXJlcyA9ICgxTEwgKiByZXMgKiBhKSAlIG1vZDsKCQl9CgkJYSA9ICgxTEwgKiBhICogYSkgJSBtb2Q7CgkJYiA+Pj0gMTsKCX0KCXJldHVybiByZXM7Cn0KaW50IG1haW4oKXsKCXNjYW5mKCIlZCIgLCAmdCk7Cglmb3IoaW50IHRjID0gMSA7IHRjIDw9IHQgOyArK3RjKXsKCQlzY2FuZigiJWQgJWQgJWQiICwgJmEgLCAmbiAsICZwKTsKCQlhbnMgPSBhOwoJCWZvcihpbnQgaSA9IDEgOyBpIDw9IG4gOyArK2kpewoJCQlhbnMgPSBwb3dlcihhbnMgLCBpICwgcCk7CgkJfQoJCXByaW50ZigiQ2FzZSAjJWQ6ICVkXG4iICwgdGMgLCBhbnMpOwoJfQp9