#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 1000000;
int main() {
    vector<int> cnt(MAXN + 1, 0);
    for (int i = 2; i <= MAXN; i++)
    {
        if (cnt[i] == 0) 
        {
            for (int j = i; j <= MAXN; j += i) {
                cnt[j]++;
            }
        }
    }
    static int pref[8][MAXN + 1];
    for (int k = 0; k <= 7; k++) 
    {
        pref[k][0] = 0;
        for (int i = 1; i <= MAXN; i++) {
            pref[k][i] = pref[k][i - 1] + (cnt[i] >= k);
        }
    }
    int Q;
    cin >> Q;
    while (Q--) 
    {
        int a, b, k;
        cin >> a >> b >> k;
        cout << pref[k][b] - pref[k][a - 1] << '\n';
    }
}
dmm