/*
 Author: 曹北健(37509)
 Result: AC Submission_id: 5274020
 Created at: Thu Mar 23 2023 21:03:16 GMT+0800 (China Standard Time)
 Problem: 6756  Time: 26    Memory: 1592
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <time.h>
#pragma warning(disable:4996 6031)
long long get_phi(long long n){
    long long phi = n, i;
    for(i = 2; i * i <= n; i++){
        if(n % i == 0){
            while(n % i == 0)
                n /= i;
            phi -= phi / i;
        }
    }
    if(n > 1)
        phi -= phi / n;
    return phi;
}
long long gcd(long long a, long long b){
    return b ? gcd(b, a % b) : a;
}
long long pow_mod(long long a, long long t, long long p){
    long long ans = 1;
    while(t--)
        ans = 1LL * ans * a % p;
    return ans;
}
int main(){
#ifdef _DEBUG
    freopen("../../input.txt", "r", stdin);
#endif // _DEBUG
    //不用开数组 因为你不知道要开多大
    //如果再让我debug时候看到 开数组的时候 int/double/whatever a[n]其中n是个变量 直接弹脑壳
    int T;
    scanf("%d", &T);
    long long a, t, p, g, ph;
    while(T--){
        scanf("%lld%lld%lld", &a, &t, &p);
        g = gcd(a, p);
        ph = get_phi(p);
        if(g == 1){
            printf("Case #1: %lld\n", pow_mod(a, t % ph, p));
        }
        else{
            if(t < ph){
                printf("Case #2: %lld\n", pow_mod(a, t, p));
            }
            else{
                printf("Case #3: %lld\n", pow_mod(a, (t % ph) + ph, p));
            }
        }
    }
#ifdef _DEBUG
    freopen("CON", "r", stdin);
    system("pause");
#endif // _DEBUG
    return 0;
}