#include<bits/stdc++.h>#define MAXSIZE 1000015#define INF 0x3f3f3f3f#define LL long long#define MOD 998244353using namespace std;bool vis[MAXSIZE];LL p[MAXSIZE],a[MAXSIZE],b[MAXSIZE];int n,cns;void GetPrime(){    cns = 1;    memset(vis,false,sizeof(vis));    vis[1] = true;    for(int i=2;i<MAXSIZE;i++)    {        if(vis[i] == false)        {            p[cns++] = i;            for(int j=i*2;j<MAXSIZE;j+=i)            {                vis[j] = true;            }        }    }}int main(){    GetPrime();    LL l,r,k,ans;    int T;    scanf("%d",&T);    while(T--)    {        scanf("%lld%lld%lld",&l,&r,&k);        ans = 0;        for(LL i=l;i<=r;i++)        {            a[i-l] = i; //记录这个数的值            b[i-l] = 1; //记录正因子个数        }        for(int i=1;p[i]*p[i]<=r && i<=cns;i++) //枚举素数        {            LL j = l/p[i] + (l%p[i]!=0);            for(j=j*p[i];j<=r;j+=p[i]) //枚举素数的倍数            {                LL sum = 0;                while(a[j-l]%p[i] == 0)                {                    sum++;                    a[j-l]/=p[i];                }                b[j-l] = (b[j-l]*((sum*k%MOD + 1)%MOD))%MOD;             }        }        for(LL i=l;i<=r;i++)        {            if(a[i-l] == 1)                ans = (ans+b[i-l])%MOD;            else                ans = (ans+b[i-l]*(k+1)%MOD)%MOD;        }        printf("%lld\n",ans);    }    return 0;}