#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;

int qpow(ull a,ull b,ull n){
    if(b==0)return 0;
	int ret=1;
	while(b){
		if(b%2==1)ret=ret*a%n;
		a=a*a%n;
		b>>=1;
	}
	return ret;
}
int T,n,k;
ull a,b;
ull f[1005]={};
int main(){
	f[0]=0;
	f[1]=f[2]=1;
	cin>>T;
	while(T--){
		cin>>a>>b>>n;
		if(n==1||a==0){cout<<0<<endl;continue;}
		for(int i=3;i<=n*n+1;i++){
			f[i]=(f[i-1]%n+f[i-2]%n)%n;
			if(f[i-1]==1&&f[i]==1){
				k=i-2;
				break;
			}
		}
		int tmp=qpow(a%k,b,k);
		cout<<f[tmp]<<endl;
	}
	
	return 0;
}