rt

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll m=998244353;
bitset<35009>v;
vector<ll>pri;
int Q,X,Y,K,N;
inline ll mod(ll a){return (a%m+m)%m;} 
inline ll fmul(ll a,ll b){
	ll ans=0;
	for(;b;a=mod(a<<=1),b>>=1){
		if(b&1)ans=mod(ans+a);
	}
	return a=ans;
}
inline ll fpow(ll x,ll p){
	if(p==1)return x;
	ll ans=1;
	for(;p;x=fmul(x,x),p>>=1){
		if(p&1)ans=fmul(ans,x);
	}
	return ans;
}
inline void solve(){
	ll ans=1;
	cin>>X>>Y>>N;
	K=Y/X;
cerr<<"K="<<K<<'\n';
	for(ll i:pri){
		if(K%i)continue;
cerr<<"i="<<i;
		ll cnt=0,tmp=0;
		for(;K%i==0;){
			cnt++,K/=i;
		}
//cerr<<",cnt="<<cnt;
		tmp+=fpow(cnt+1,N);
//cerr<<",tmp(1)="<<tmp;
//cerr<<",fpow(i+1,N)="<<fpow(i+1,N);
		tmp=mod(tmp+=fpow(cnt-1,N));
//cerr<<",tmp(3)="<<tmp;
		tmp=mod(tmp-=(fpow(cnt,N)<<1));
//cerr<<",tmp(2)="<<tmp;
//cerr<<",fpow(i,N)="<<fpow(i,N);

//cerr<<",fpow(i-1,N)="<<fpow(i-1,N);
		ans=fmul(ans,tmp);
//cerr<<",ans="<<ans;
//cerr<<",K="<<K<<'\n';
		if(i>K||K==1)break;
	}
	printf("%lld\n",mod(ans));
	return; 
}
int main(){
	for(int i=2;i<=35000;i++){
		if(v[i]==0){
			pri.push_back(i);
		}
		for(int j:pri){
			if(i*j>35000)break;
//cerr<<"i="<<i<<",j="<<j<<'\n';
			v[i*j]=1;
		}
	}
for(int i:pri)cerr<<i<<' ';cerr<<'\n';
//cerr<<fpow(10,10);
//cerr<<madd(10,-998244353);
//cerr<<mod(1000000000);
//cerr<<fpow(8767869,998244352);
	cin>>Q;
	for(int i=1;i<=Q;i++)solve();
	return 0; 
}

快速幂没挂