#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+20;
const int M=1e6;
const ll mod=998244353;
ll L,R,k,T,f[N],pw[N],vis[N],p[N],pn=0;
void init()
{
    for(int i=2;i<=M;i++)
    {
        if(!vis[i])
        {
            p[pn++]=i;
            for(int j=i+i;j<=M;j+=i)
                vis[j]=1;
        }
    }
}
int main()
{
    init();
    cin>>T;
    while(T--)
    {
        ll ans=0;
        scanf("%lld%lld%lld",&L,&R,&k);
        if(L==1)
            ans++,L++;
        for(ll i=L;i<=R;i++)
            f[i-L]=i,pw[i-L]=1;
        for(int i=0;i<pn&&p[i]*p[i]<=R;i++)
        {
            //p[i]μ?±?êy?aê? 
            ll st=L,cnt;
            if(L%p[i])
                st=(L/p[i]+1)*p[i];
            for(ll j=st;j<=R;j+=p[i])
            {
                cnt=0;
                while(f[j-L]%p[i]==0)
                    cnt++,f[j-L]/=p[i];    
                pw[j-L]=(pw[j-L]*(cnt*k+1))%mod;        
            }
        }
        for(ll i=L;i<=R;i++)
        {
        //    cout<<i<<‘ ‘<<pw[i-L]<<endl;
            if(f[i-L]==1)
                ans=(ans+pw[i-L])%mod;
            else//该数为素数
                ans=(ans+pw[i-L]*(k+1))%mod;
        }
        printf("%lld\n",ans);        
    }
    return 0;
}