#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