/*

 问题

 输入a，b，n(0<a,b<2^64(a and bwill not both be zero) and 1<n<1000)

 计算并输出f(a^b)%n的结果

 其中f(i)是斐波那契数列

 解题思路

 所有的结果都是f(i)对n取模,不妨设F(i)=f(i)%n。不难发现当F(i),F(i+1)出现重复的时候，整个序列就开始出现重复。

 所以设周期为mod，计算出一个循环周期F(0)~f(n^2-1),计算出F(a^b % mod)即可。

 */

 #include<cstdio>

 #include<iostream>

 #include<string>

 using namespace std;

 const int N=;

 int F[N],mod;

 int makeF(int n);

 int kpow(unsigned long long a,unsigned long long p);

 int main()

 {

     unsigned long long a,b;

     int n,T;

     scanf("%d",&T);

     while(T--){

         cin>>a>>b>>n;

         if(n==||!a) {printf("0\n");continue;}

         mod=makeF(n);

         printf("%d\n",F[kpow(a%mod,b)]);

     }

     return ;

 } 

 int kpow(unsigned long long a,unsigned long long p){

     int ans=;

     for(;p;p>>=,a=(a*a)%mod) if(p&) ans=(ans*a)%mod;

     return ans;

 }

 int makeF(int n)

 {

     F[]=;

     F[]=;

     F[]=;

     int l=n*n+;

     for(int i=;i<=l;i++){

         F[i] = ((F[i-]%n)+(F[i-]%n))%n;

         if(F[i]==F[] && F[i-]==F[]){

             return i-;

         }

     }

 }