UVA-11582

#include<iostream>
#include<string.h>
#include<algorithm>
#include<map>
#include<stdio.h>
#define ll long long
#define ULL unsigned long long
using namespace std;
const int maxx = 1e6+5;
ll fac[maxx];
int pow_mod(ULL a,ULL n,ULL m){
  if (n==0) return 1;
  ULL x = pow_mod(a,n/2,m);
  ULL ans = (ll)x*x%m;
  if (n%2==1)ans=ans*a%m;
  return ans;
}
int main(){
  int n;
  unsigned long long a,b;
  int t,base;
  scanf("%d",&t);
  while(t--){
     cin>>a>>b>>n;
     fac[1]=1;
     fac[0]=0;
     fac[1]=fac[1]%n;
     for(int i=2;i<=n*n+100;i++){
        fac[i]=(fac[i-1]+fac[i-2])%n;
        if (fac[i]==fac[1] && fac[i-1]==fac[0]){
            base=i-1;
            break;
        }
     }
     int v=pow_mod(a%base,b,base);
     printf("%lld\n",fac[v]);
  }
  return 0;
}