#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
#define fir first
#define sec second
#define pb(x) push_back(x)
#define mem(A, X) memset(A, X, sizeof A)
#define REP(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define rep(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))
#define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
typedef pair<long,long> pll;
int T,n;
const int mod=1e9+;
const int maxn=1e3+;
typedef unsigned long long ULL;
ULL qsm(ULL a, ULL b, ULL mod) // 0<=a<=ULL 0<=b<=ULL
{
a=a%mod;
ULL res=;
while(b)
{
//a=a%mod;(有时候n的值太大了会超出long long的储存，所以要先取余)
if(b&)//&位运算：判断二进制最后一位是0还是1，&的运算规则为前后都是1的时候才是1；
res=res*a%mod;
b=b>>;//相当于除以2；
a=a*a%mod;
}
return res;
}
ULL f[maxn*maxn+];
int main()
{
freopen("in.txt","r",stdin);
//while(cin>>n)
while(cin>>T&&T)
{
REP(kase,,T) {
ULL ans;
ULL a,b,n;
cin>>a>>b>>n;
if(a==||n==) ans=;
else
{
f[]=;
f[]=;
int M;
REP(i,,n*n+)
{
f[i]=(f[i-]+f[i-])%n;
if(f[i]==f[]&&f[i-]==f[])
{
M=i-;
break;
}
}
ULL t=qsm(a,b,M);
ans=f[t];
}
cout<<ans<<endl;
}
}
return ;
}
/*
note :
对于循环节类的问题,只需要找到刚开始的起始项,之后找到周期,利用周期的一致性,将查询到
项直接进行周期M取模即可,注意f[0]是否进行了赋值,如果没有的话还需要f[0]=f[M].
debug : 范围比较大需要用到ull
re的原因有可能是因为数据类型不一致,(返回 runtime error )
for(int i=1;i<=(unsigned long long)100;i++)
optimize: 分析出n的范围,预处理出来,可以避免大量的查询.分析出来了所有的基本可能情况.
改进快速幂取模,
命名 进行程序变量的命名的时候,最好直接指代原来的变量例如 预处理n的时候,直接就是n就可以.
REP(n,2,maxn)
*/
