取余里面的减法得防止出现负数
另外这个题的思维过程用了GCD和LCM的乘法性质
这个题本身可以不除以x来做，除以x可以降低计算量，这是一个trick。
如果不除以x，那么看到这个题就该思考，对于一个a序列，质因数分解之后，每个质数的指数区间都在x对应质数的指数，y对应的质数的指数的范围内，并且还得取到两个最值。

至少有，两个约束条件，这个情况下只能用容斥

#include<bits/stdc++.h>

using namespace std;
const int p = 998244353;
const int N = 2e5+4;
using ll = long long;
int Q;
//分解质因数取35就行了
int k[35];
int cnt=0;
void get_prime(int x){
    cnt=0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            k[++cnt]=0;
            while(x%i==0){
                // x%=i;
                x/=i;
                k[cnt]++;
            }
        }
    }
    if(x!=1)
        k[++cnt]=1;

}

ll q_pow(ll a,ll n){
    ll res=1;
    while(n){
        if(n&1)
            res=(res*a)%p;
        n/=2;
        a=(a*a)%p;
    }
    return res;
}
int main(){
    scanf("%d",&Q);
    while(Q--){
        int x,y,n;
        scanf("%d%d%d",&x,&y,&n);
        //构造b序列，为a序列全部除以x，那么b序列的gcd为1，lcm为y/x;
        get_prime(y/x);
        ll ans=1;
        for(int i=1;i<=cnt;i++){
            //对于每个质因数，有一共k[i]+1种指数
            //这里的选择里面得保证至少有一个指数为0，有一个为k[i]
            //可以写成C(2,n)*((k[i]+1)^(n-2)),这个写法不对
            //这个写法会造成重复和遗漏，对于这种至少存在，多约束，最好使用容斥原理
            //(k[i]+1)^n*(k[i])^n+(k[i]-1)^n
            ll temp=0;
            temp=(1ll*temp+q_pow(k[i]+1,n))%p;
            temp=(1ll*temp-q_pow(k[i],n))%p;
            temp=(1ll*temp+p)%p;
            temp=(1ll*temp-q_pow(k[i],n))%p;
            temp=(1ll*temp+p)%p;
            temp=(1ll*temp+q_pow(k[i]-1,n))%p;
            //这里应该把每个质因数的取法给乘起来，这样才对
            ans=(ans*temp)%p;
        }
        cout<<ans<<endl;
    }

    return 0;
}
/*
3
3 6 2
12 144 3
233 251640 10

2
72
905954656
*/