#include <bits/stdc++.h>

using namespace std;

ifstream f("guinness.in");
ofstream g("guinness.out");

long long fast_pow(long long base,int exp,int MOD) {
    long long remainder=1;
    while(exp!=1)
        if(exp%2==0)
            base*=base,exp/=2,base%=MOD;
        else
            remainder*=base,remainder%=MOD,base*=base,base%=MOD,exp/=2;            
    return (base*remainder)%MOD;
}

long long A,MOD,N;
char B[100001];

int main() {
    int T;
    f>>T;    
    while(T--) {
        long long ans=1;
        f>>A>>B>>MOD;
        N=strlen(B);       
        for(int i=N-1;i>=0;i--)
        {
            ans*=fast_pow(A,B[i]-'0',MOD);
            A=fast_pow(A,10,MOD);
        }
        g<<ans<<'\n';
    }
}