#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

typedef long long ll;

const int maxn=1e6+;

const int mod=;

ll prime[maxn];

int vis[maxn];

ll d[maxn],arr[maxn];

// 比较大的数组放全局

int ret;

void init()

{

    memset(vis,,sizeof(vis));

    ret=;

    for(ll i=;i<maxn;i++)

    {

        if(!vis[i])

        {

            prime[++ret]=i;

            for(ll j=i*;j<=maxn;j+=i) vis[j]=;

        }

    }

}

void solve(ll l,ll r,ll k)

{

    for(ll i=;i<=ret;i++)

    {

        ll pos=(l+prime[i]-)/prime[i]*prime[i];// 定位

        while(pos<=r)

        {

            int zz=;//

            while(arr[pos-l]%prime[i]==)

            {

                zz++;

                arr[pos-l]/=prime[i];

            }

            d[pos-l]*=(k*zz+);

            d[pos-l]%=mod;

            pos+=prime[i];

        }

    }

    ll ans=;

    for(ll i=l;i<=r;i++)

    {

        if(arr[i-l]==) ans=(ans+d[i-l])%mod;

        else ans=(ans+d[i-l]*(k+))%mod;//唯一分解定理

    }

    printf("%lld\n",ans);

}

// 数差在一定范围 就可以用偏移数组

int main()

{

    int t;

    scanf("%d",&t);

    init();

    while(t--)

    {

        ll l,r,k;

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

        for(ll i=l;i<=r;i++)

        {

            arr[i-l]=i;

            d[i-l]=;

        }

        solve(l,r,k);

    }

    return ;

}