#include <bits/stdc++.h>
using namespace std;
const int ms = 1025000;
int f[ms], mark[ms], d[ms];
typedef pair<int, int> pii;
vector<pii> v;

int main(){
    for(int i = 0; i < ms; i++)
        f[i] = i;

    memset(mark, 0, sizeof mark);
    for(int i = 2; i < ms; i++)
        if(!mark[i])
            for(int j = i; j < ms; j += i){
                mark[j] = true;
                f[j] -= f[j]/i;
            }

    for(int i = 1; i < ms; i++){
        int ans = 0, at = i;
        for(; at != 1; at = f[at])
            ans++;

        v.push_back({ans, i});
    }

    sort(v.begin(), v.end());
    int q, n, m, k;
    cin >> q;
    for(int i = 0; i < q; i++){
        scanf("%d%d%d" , &n, &m, &k);
        int ans = upper_bound(v.begin(), v.end(), pii(k, m))-lower_bound(v.begin(), v.end(), pii(k, n));
        cout << ans << endl;
    }
    return 0;
}