prime

//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<fstream>
#include<cmath>

#define long long long
#define nln '\n'

const long N = 1e6+10;

using namespace std;

// Global variables: q, a, b, k

long q;
vector<long> a, b, k;
fstream f1;

void data()
{
    f1.open("prime.inp", ios:: in);
    cin >> q;
    a.resize(q+1, 0);
    b.resize(q+1, 0);
    k.resize(q+1, 0);
    for (long i = 1; i <= q; ++i)
        cin >> a[i] >> b[i] >> k[i];
    f1.close();
}

vector<long> sie(N, 1), cou(N, 0);

void eratosthenes()
{
    sie[0] = 0;
    sie[1] = 0;

    for (long i = 2; i < N; ++i)
    {
        if (sie[i])
        {
            cou[i] = 1;
            for (long j = 2*i; j < N; j += i)
            {
                sie[j] = 0;
                ++cou[j];
            }
        }
    }
}

long tot[8][N];

void cumulative_total()
{
    for (long i = 2; i < N; ++i)
    {
        ++tot[cou[i]][i];
        for (long j = 1; j <= 7; ++j)
            tot[j][i] += tot[j][i-1];
    }
}

vector<long> ans(1, 0);

void find()
{
    for (long i = 1; i <= q; ++i)
        ans.push_back(tot[k[i]][b[i]]-tot[k[i]][a[i]-1]);
}

void process()
{
    eratosthenes();
    cumulative_total();
    find();
}

void view()
{
    for (long i = 1; i <= q; ++i)
        cout << ans[i] << nln;
}

int main()
{
    data();
    process();
    view();
    return 0;
}