N-Factorful

#include<bits/stdc++.h>
#define int long long
#define fastio  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cout << #x << "--> " << x << endl;
#define pii pair<int, int>
using namespace std;
#define M 1000000
int marked[M + 2];
vector<int>primes;
void sieve(void)
{
    for(int i = 3; i * i <= M; i += 2)
    {
        if(marked[i] == false)
        {
            for(int j = i * i; j <= M; j += i + i)
                marked[j] = true;
        }
    }
    primes.push_back(2);
    for(int i = 3; i <= M; i += 2)
    {
        if(marked[i] == false)
            primes.push_back(i);
    }
}
bool isprime(int n)
{
    if(n <= 1) return false;
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    return (marked[n] == false);
}
int distinctprime(int n)
{
    int cnt = 0;
    for(int i = 0; primes[i] * primes[i] <= n; i++)
    {
        if(n % primes[i] == 0)
        {
            cnt++;
            while(n % primes[i] == 0) n /= primes[i];
        }
    }
    if(n > 1) cnt++;
    return cnt;
}
vector<int>vec[M];
void precal()
{
    for(int i = 1; i <= M; i++)
    {
        if(isprime(i)) vec[1].push_back(i);
        else vec[distinctprime(i)].push_back(i);
    }
}
main()
{
    fastio;
    sieve();
    precal();
    int tc; cin >> tc;
    while(tc--)
    {
        int a, b, n; cin >> a >> b >> n;
        vector<int>tmp = vec[n];//take all the numbers having n distinct factors
        int idx1 = lower_bound(tmp.begin(), tmp.end(), a) - tmp.begin();
        int idx2 = upper_bound(tmp.begin(), tmp.end(), b) - tmp.begin();
        cout << idx2 - idx1 << endl;
    }
}