#include<bits/stdc++.h>
using namespace std;
struct Prime{int p,pt,t;}a[50];//p表示素数，pt表示p^t，t表示P中含有多少个p
int tot,_;
void spilt(int p){
	tot=0;
	for(int i=2;i*i<=p;i++)
		if(p%i==0){
			a[++tot].p=i,a[tot].pt=1,a[tot].t=0;
			for(;p%i==0;p/=i)a[tot].pt*=i,a[tot].t++;
		}
	if(p>1) a[tot].p=a[++tot].pt=p,a[tot].t=1;
}
int kuai(int a,int b,int mod){//快速幂
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
	return ans;
}
int get_Step(int a,int n,int mod){//求阶
	int ans=n;
	for(int i=2;i*i<=n;i++)
		if(n%i==0){
			while(ans%i==0&&kuai(a,ans/i,mod)==1)ans/=i;
			for(;n%i==0;n/=i);
		}
	if(kuai(a,ans/n,mod)==1)ans/=n;
	return ans;
}
int ans;
void solve(int A,int B,int mod,int phi){
	int c=get_Step(B,phi,mod),y=phi/c,G=__gcd(A,phi);
	if(y%G)ans=0;
	ans*=G;
}
int main(){
	scanf("%d",&_);
	while(_--){
		int A,B,k;
		scanf("%d%d%d",&A,&B,&k);
		int P=2*k+1;
        B%=P;
		ans=1;
		spilt(P);//先将P分解质因数
		for(int i=1;i<=tot;i++){
			int p=a[i].p,t=a[i].t,pt=a[i].pt;
			if(!ans)break;
			if(B%pt==0) ans*=kuai(p,t-(t+A-1)/A,1e9);
			else{
				int Z=0,b=B;
				for(;b%p==0;Z++,pt/=p,t--,b/=p);
				if(Z%A)ans=0;
				else{
					solve(A,b,pt,pt-pt/p);
					ans*=kuai(p,Z-Z/A,1e9);
				}
			}
		}
		printf("%d\n",ans);
	}
}