/**
题目：Colossal Fibonacci Numbers! UVA 11582
链接：https://vjudge.net/problem/UVA-11582
题意:f[0] = 1, f[1] = 1; 给定一个n，求f[a^b]%n的结果。a,b达到2^64 - 1大。
思路：a,b很大，用无符号长整型;我还是太菜了，自己没想出来。这道题很显然是找循环节的题。但我不知怎么找。
lrj P316
思路就是，由于fibonacci数是由前两个数相加得来，又%n;所以所有fibonacci取余后，结果都在1000以内。
两个连续的数最多只有1000×1000种。所以循环节就会出现。
我一开始以为可能是混循环或者纯循环两种情况。然后搞得很麻烦。
实际上只有一种情况：纯循环；
证明：假设存在混循环，f[0] f[1] f[2] ... f[i] f[i+1] ... f[j] f[j+1]...
f[i]==f[j], f[i+1]==f[j+1]; 由于f[i+1] = f[i]+f[i-1] , f[j+1] = f[j]+f[j-1] 所以显然f[i-1]==f[j-1]; 那么f[i-1] f[i] f[j-1] f[j]又是一个循环节。同理一直推到f[0] f[1]开始的循环。 所以都是纯循环。 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3+;
const double eps = 1e-;
int f[maxn*maxn];
ull a, b;
int n;
ll PowMod(int mod)
{
ll p = ;
a %= mod;
ll x = a;
while(b>){
if(b&) p = p*x%mod;
x = x*x%mod;
b >>= ;
}
return p;
}
void solve()
{
f[] = ;
f[] = ;//n = 1 的时候 这里为0
int ed;
for(int i = ; i <= n*n; i++){
f[i] = f[i-]+f[i-];
f[i] %= n;
if(f[i-]==f[]&&f[i]==f[]){
ed = i-; ///[st, ed]
break;
}
}
ll pos = PowMod(ed);
printf("%d\n",f[pos]);
}
int main()
{
int T;
cin>>T;
while(T--){
scanf("%llu%llu%d",&a,&b,&n);
if(a==||n==){///处理0^ei的情况，以及对1取模值肯定为0；
printf("0\n"); continue;
}
solve();
}
return ;
}