#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int T,a,b,k;
vector<pair<int,int>> fractor_divide(int n) {
	vector<pair<int,int>> ans;
	ffor(i,2,n/i) if(n%i==0) {
		int cnt=0;
		while(n%i==0) cnt++,n/=i;	
		ans.push_back({i,cnt});
	}
	if(n!=1) ans.push_back({n,1});
	return ans;
}
int calc_phi(int n) {
	int ans=n;	
	ffor(i,2,n/i) if(n%i==0) {
		int cnt=0;
		while(n%i==0) cnt++,n/=i;
		ans=ans/i*(i-1);
	}
	if(n!=1) ans=ans/n*(n-1);
	return ans;
}
pair<int,int> exgcd(int a,int b) {
	if(!b) return {1,0};
	auto pr=exgcd(b,a%b);
	return {pr.second,pr.first-a/b*pr.second};
}
int calc_inv(int x,int mod) {
	return (exgcd(x,mod).first%mod+mod)%mod;
}
int qpow(int base,int p,int mod) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%mod;
		base=base*base%mod,p>>=1;	
	}
	return ans;
}
int check(int v,int n,vector<int>& p,int phi) {
	for(auto id:p) if(qpow(v,phi/id,n)==1) return 0;
	return 1;
}
int get_root(int n) {
	int phi=calc_phi(n);
	auto vc=fractor_divide(phi);
	vector<int> p;
	for(auto pr:vc) p.push_back(pr.first);
	ffor(i,2,n) if(check(i,n,p,phi)) return i;
}
int get_log(int g,int v,int n) {
	unordered_map<int,int> mp;
	int tmp=1,B=sqrt(n);
	ffor(i,0,B-1) {
		if(tmp==v) return i;
		mp[tmp]=i,tmp=tmp*g%n;	
	}
	int inv=calc_inv(tmp,n);
	tmp=1;
	ffor(i,0,B+1) {
		if(mp.count(v*tmp%n)) return i*B+mp[v*tmp%n];
		tmp=tmp*inv%n;	
	}
	return -1;
}
int calc(int a,int b,int p,int k) {
	int n=1;
	ffor(i,1,k) n=n*p;
	b%=n;
	if(b%n==0) {
		int ans=1,tmp=n;
		ffor(j,1,k-1) {
			tmp/=p;
			if(a*j>=k) ans+=tmp/p*(p-1);
		}
		return ans;
	}if(b%p==0) {
		int vp=0,B=b;
		while(B%p==0) vp++,B/=p;
		if(vp%a) return 0;
		int mul=1;
		ffor(i,1,vp-vp/a) mul=mul*p;
		return calc(a,B,p,k-vp)*mul;	
	}
	int g=get_root(n),phi=calc_phi(n);
	int t=get_log(g,b,n);
	if(t%__gcd(a,phi)) return 0;
	return __gcd(a,phi);
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>a>>b>>k;
		int ans=1;
		auto vc=fractor_divide(2*k+1);
		for(auto pr:vc) ans=ans*calc(a,b,pr.first,pr.second);
		cout<<ans<<'\n';
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int T,a,b,k;
vector<pair<int,int>> fractor_divide(int n) {
	vector<pair<int,int>> ans;
	ffor(i,2,n/i) if(n%i==0) {
		int cnt=0;
		while(n%i==0) cnt++,n/=i;	
		ans.push_back({i,cnt});
	}
	if(n!=1) ans.push_back({n,1});
	return ans;
}
int calc_phi(int n) {
	int ans=n;	
	ffor(i,2,n/i) if(n%i==0) {
		int cnt=0;
		while(n%i==0) cnt++,n/=i;
		ans=ans/i*(i-1);
	}
	if(n!=1) ans=ans/n*(n-1);
	return ans;
}
pair<int,int> exgcd(int a,int b) {
	if(!b) return {1,0};
	auto pr=exgcd(b,a%b);
	return {pr.second,pr.first-a/b*pr.second};
}
int calc_inv(int x,int mod) {
	return (exgcd(x,mod).first%mod+mod)%mod;
}
int qpow(int base,int p,int mod) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%mod;
		base=base*base%mod,p>>=1;	
	}
	return ans;
}
int check(int v,int n,vector<int>& p,int phi) {
	for(auto id:p) if(qpow(v,phi/id,n)==1) return 0;
	return 1;
}
int get_root(int n) {
	int phi=calc_phi(n);
	auto vc=fractor_divide(phi);
	vector<int> p;
	for(auto pr:vc) p.push_back(pr.first);
	ffor(i,2,n) if(check(i,n,p,phi)) return i;
}
int get_log(int g,int v,int n) {
	unordered_map<int,int> mp;
	int tmp=1,B=sqrt(n);
	ffor(i,0,B-1) {
		if(tmp==v) return i;
		mp[tmp]=i,tmp=tmp*g%n;	
	}
	int inv=calc_inv(tmp,n);
	tmp=1;
	ffor(i,0,B+1) {
		if(mp.count(v*tmp%n)) return i*B+mp[v*tmp%n];
		tmp=tmp*inv%n;	
	}
	return -1;
}
int calc(int a,int b,int p,int k) {
	int n=1;
	ffor(i,1,k) n=n*p;
	b%=n;
	if(b%n==0) {
		int ans=1,tmp=n;
		ffor(j,1,k-1) {
			tmp/=p;
			if(a*j>=k) ans+=tmp/p*(p-1);
		}
		return ans;
	}
	if(b%p==0) {
		int vp=0,B=b;
		while(B%p==0) vp++,B/=p;
		if(vp%a) return 0;
		int mul=1;
		ffor(i,1,vp-vp/a) mul=mul*p;
		return calc(a,B,p,k-vp)*mul;	
	}
	int g=get_root(n),phi=calc_phi(n);
	int t=get_log(g,b,n);
	if(t%__gcd(a,phi)) return 0;
	return __gcd(a,phi);
}
signed main() {
	ios::sync_with_stdio(False),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>a>>b>>k;
		int ans=1;
		auto vc=fractor_divide(2*k+1);
		for(auto pr:vc) ans=ans*calc(a,b,pr.first,pr.second);
		cout<<ans<<'\n';
	}
	return 0;
}