原则1：n的余数最多有n种，所以最多n^2就会一个循环，就像400前后同一天的星期几也一样，是个至少要满足的循环
n是1~1000，f函数从第3项开始算时间超出，所以直接打表
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1000+5;
int ans[maxn][maxn*6],p[maxn]; //p记录周期 int pow_mod(int a,int b,int n)
{if(b==0) return 1;int x=pow_mod(a,b/2,n);int ans=(int)((long long)(x*x)%n);if(b%2) ans=(ans*a)%n;return ans;
}
void init()
{for(int n=2;n<=1000;n++){ans[n][0]=0;ans[n][1]=1;for(int i=2;;i++){ans[n][i]=(ans[n][i-1]+ans[n][i-2])%n;if(ans[n][i-1]==0&&ans[n][i]==1){p[n]=i-1;break;}}}
} int main()
{int t;scanf("%d",&t);init();int n;unsigned long long a,b;while(t--){cin>>a>>b>>n;cout<<(a==0||n==1?0:ans[n][pow_mod(a%1000,b%1000,p[n])])<<endl;}return 0;
}