#include <cstdio>
#include <cstring>
using namespace std;
typedef long long lolo;
const int MAXpdN=10,MOD=998244353;
int Q,X,Y,N,buc[MAXpdN];
lolo fastpow(lolo a,lolo b,lolo p){
	a%=p;lolo res=1;
	while(b){
		if(b&1)(res*=a)%=p;
		(a*=a)%=p,b>>=1;
	}
	return res;
}
lolo solve(int val,int n){
	memset(buc,0,sizeof(buc));
	int bcnt=0,cval=val;
	for(int i = 2;i*i<=val;i++){
		if(cval%i==0){
			bcnt++;while(cval%i==0){
				buc[bcnt]++,cval/=i;
			}
		}
	}
	if(!bcnt)bcnt++,buc[bcnt]++;
	lolo ans=1,cres;
	for(int i = 1;i <= bcnt;i++){
		int t=buc[i];
		cres=((fastpow(t+1,n,MOD)-(fastpow(t,n,MOD)*2%MOD)+MOD)%MOD+fastpow(t-1,n,MOD))%MOD;
		(ans*=cres)%=MOD;
	}
	return ans;
}
int main(){
	scanf("%d",&Q);
	for(int i = 1;i <= Q;i++){
		scanf("%d%d%d",&X,&Y,&N);
		printf("%lld\n",solve(Y/X,N));
	}
	return 0;
}