#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{

    int n,p;
    long long int a, b1, m,ans,l;
    cin>>n;
    for(int i =0; i<n; i++)
    {
            int c=0, sum=0;
            char b[250];
         //   cin>>a>>b>>m;
         scanf("%lld",&a);
	scanf("%s",&b);

	scanf("%lld",&m);
            //itoa (b1,buffer,10);
            l=strlen(b);
           // int b=0;
            for(int i=0;i<l;i++)
            {
                    for(int j=0;j<l-i;j++)
                   b[i]=b[i]*3;
                    sum=sum+b[i];
              }

            ans=a;
            while(sum>1)
            {
                      if(sum&1==1)
                      ans=(ans*a)%m;
                      a=a*a;
                      sum=(sum>>1)%m;

            }
   printf("%d",ans);
    //cout<<ans<<endl;
}


    return 0;
}