#include <bits/stdc++.h>
#define gc getchar()
#define pc(c) putchar(c)
#define int long long
using namespace std;
typedef long long unsigned llu,ull;
constexpr signed N=1007;
int a,b,n,loop;
signed vst[N][N];
ull fib[2000007];
inline ull read(){
	register signed t=0,f=1;
	register char c=gc;
	while(c!='-'&&(c<'0'||c>'9')) c=gc;
	while(c>='0'&&c<='9') t=10*t+(c^48),c=gc;
	return f*t;
}
inline void write(ull x){
	if(!x) return (void)pc('0');
	static char c[53]={""};
	static signed cc=0;
	while(x) c[++cc]=x%10,x/=10;
	while(cc) putchar(c[cc--]|48);
}
inline ull qp(ull a,ull b,ull p){
	ull s=1ull;
	a%=p;
	while(b){
		if(b&1ull) s=(s*a)%p;
		a=(a*a)%p;
		b>>=1;
	}
	return s;
}
void solve(){
	a=read(),b=read(),n=read();
	memset(vst,0,sizeof vst);
	fib[0]=0,fib[1]=1;
	vst[0][1]=1;
	loop=0;
	if(n==1||a==0){
		puts("0");
		return;
	}
	for(signed i=2;i<=n*n+1;++i){
		fib[i]=(fib[i-1]+fib[i-2])%n;
		if(vst[fib[i-1]][fib[i]]){
			loop=i-vst[fib[i-1]][fib[i]];
			break;
		}
		vst[fib[i-1]][fib[i]]=i;
	}
	ull pos=qp(a,b,loop);
	write(fib[pos]%n),puts("");
}
signed main(){
	signed t=read();
	while(t--) solve();
	return 0;
}