/*

* @Author: Lyucheng

* @Date:   2017-08-03 13:13:45

* @Last Modified by:   Lyucheng

* @Last Modified time: 2017-08-04 11:25:19

*/

/*

 题意：给你一个区间[l,r]让你求区间内每个数的k次方因子数的总和

 思路：比赛的时候想出来 i^k的因子是 (n1*k+1)*(n2*k+1)*...*(np*k+1),但是没想出来怎么优化，素数枚举

    很烦，四场比赛每次差一点，比赛的时候想的是枚举[l,r]之间的数，优化到8300ms,实在没法优化了，应

    该反过来想，枚举从[l,r]的素因子，因为i素因子的个数远小于i,大多数在sqrt i内，最多只有一个在sqrt i

    之外。

*/

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#define LL long long

#define mod 998244353

#define MAXN 1000005

using namespace std;

int t;

LL l,r,k;

LL res;

LL d[MAXN];

LL pos[MAXN];

bool prime[MAXN];

LL p[MAXN];

int tol;

void init(){

    tol=;

    for(int i=;i<MAXN;i++){

        prime[i]=true;

    }

    prime[]=prime[]=false;

    for(int i=;i<MAXN;i++){

        if(prime[i])

            p[tol++]=(LL)i;

        for(int j=;j<tol&&i*p[j]<MAXN;j++){

            prime[i*p[j]]=false;

            if((LL)i%p[j]==) break;

        }

    }

}

int main(){

    // freopen("in.txt", "r", stdin);

    // freopen("out.txt", "w", stdout);

    init();

    scanf("%d",&t);

    while(t--){

        res=;

        scanf("%I64d%I64d%I64d",&l,&r,&k);

        for(LL i=l;i<=r;i++){

            d[(int)(i-l)]=;

            pos[(int)(i-l)]=i;

        }

        for(int i=;i<tol;i++){//枚举所有的素数

            if(p[i]<=) continue;

            LL cnt=(l+p[i]-)/p[i]*p[i];//找出[l,r]区间内的第一个p[i]的倍数

            if(cnt-l<||cnt-l>r-l) continue;

            for(int j=cnt-l;j<=r-l;j+=p[i]){

                LL cur=;

                while(pos[j]&&pos[j]%p[i]==){

                    cur++;

                    pos[j]/=p[i];

                }

                d[j]*=(cur*k+);

                d[j]%=mod;

            }

        }

        for(int i=;i<=r-l;i++){

            if(pos[i]==)

                res+=d[i];

            else

                res+=d[i]*(k+);

            res%=mod;

        }

        printf("%I64d\n",res);

    }

    return ;

}