#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
#define ll long long
#define fall(a,c) for(auto &a:c)
#define all(k) k.begin(),k.end()
#define endl '\n'

const int P = 2e6+5;
vector<ll> phi(P+1);
void PHI(){//get prime factors and calculate phi
    for(ll i=1;i<P;i++)phi[i]=i;
    for(ll i=2;i<P;i++){//O(N)
        if(phi[i]==i){//n is prime
            for(ll j=i;j<P;j+=i){//O(logi)
                //i is a prime factor of j
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}

ll memo[P];
ll depth(ll n){
    if(n==1) return 0;
    if(memo[n]!=-1) return memo[n];
    return memo[n] = 1+depth(phi[n]);
}
vector<ll> sk[20];

#define endl '\n'
int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);
    PHI();
    memset(memo, -1, sizeof memo);
    int t; cin>>t;
    for(int i=1;i<=1000000;i++){
        if(depth(i)<20)
            sk[depth(i)].pb(i);
    }


    while(t--){
        int n,m,k;
        cin>>m>>n>>k;
        auto ans = int(upper_bound(all(sk[k]),n)-sk[k].begin()) - int(lower_bound(all(sk[k]),m)-sk[k].begin());
        cout<<ans<<endl;
    }



    return 0;
}