#define ONLINE_JUDGE 1
/**********************************************************************\
|           _______  _     _____    ____   ___     _                   |
|          |___   _|(_)   / ___/   / _  | |   \   | |                  |
|              | |  | |  / /___   / /_| | | |\ \  | |                  |
|           _  | |  | | /___  /  /  __  | | | \ \ | |                  |
|           \ \| |  | | ___/ /  / /   | | | |  \ \| |                  |
|            \___/  |_|/____/  /_/    |_| |_|   \___|                  |
|                  Computer Science and Engineering                    |
|  Bangabandhu Sheikh Mujibur Rahman Science and Technology University |
|         devskill:jisancse||uva:jishan047||github:jisan047            |
\**********************************************************************/

                /********************\
                |                    |
                |    lets try.....   |
                |                    |
                \********************/

#include<bits/stdc++.h>
using namespace std;

///pre-processing
#define     gcd(a, b)       __gcd(a,b)
#define     lcm(a, b)       (a * b) / gcd(a, b)
#define     loop(i, n)      for(int i=0;i<n;i++)
#define     all(x)          x.begin(),x.end()
#define     mem(a, x)       memset(a,x,sizeof a)
#define     endl            '\n'
#define     ss              second
#define     ff              first
#define     TN              typename

///input functions
int Int(){int x;scanf("%d",&x);return x;}
long long Long(){long long x;scanf("%lld",&x);return x;}
double Double(){double x;scanf("%lf",&x);return x;}

///input functions shorting
#define Int Int()
#define Long Long()
#define Double Double()
#define Float Float()

///Constants
const int N = (int) 1e5 + 5;
//const long long MOD = (int) 1e9 + 7;
//Trying to do something.
//()()()()()()()()() ..... ()()()()()()()()()()()()
//~~~~~~~~~~~~~~~~~~~~~~Get Ready~~~~~~~~~~~~~~~~~~~~~

///debugger

///end
unsigned long long peasant(unsigned long long a, unsigned long long b, unsigned long long MOD){
    unsigned long long res = 0;
    while(b){
        if(b & 1){res += (a % MOD), res %= MOD;}
        a <<= 1;
        a %= MOD;
        b >>= 1;
    }
    return res;
}
unsigned long long bigMod (unsigned long long base, unsigned long long power, unsigned long long MOD){
    long long res = 1;
    while (power){
        if (power & 1){
            res = peasant(res, base, MOD) % MOD;
        }
        base = peasant(base, base, MOD) % MOD;
        power = power >> 1;
    }
    return res;
}

// loading..................

int main()
{
    int t = Int, cs = 0;
    while(t--){
        printf("Case %d: ", ++cs);
        unsigned long long a, b, c;
        cin >> a >> b >> c;
        cout << bigMod(a, b, c) <<endl;
    }
    return 0;
}