#include <algorithm>
#include <fstream>

using namespace std;

ifstream in("reginald.in");
ofstream out("reginald.out");

#define N 1000005
#define NRMAX 4000005
#define PMAX 7

int n;
char v[NRMAX];
int d[NRMAX];
int rez[N];
char s[30];

struct query
{
    int x, y;
    short int p;
    int poz;
};

query a[N];

int cmp(query q1, query q2)
{
    return q1.p < q2.p;
}

int main()
{
    in >> n;

    in.getline(s, sizeof(s));

    short c;
    for(int i = 1; i <= n; i++)
    {
        c = 0;
        in.getline(s, sizeof(s));

        while(s[c] <= '9' && s[c] >= '0')
        {
            a[i].x *= 10;
            a[i].x += s[c] - '0';
            c++;
        }
        c++;
        while(s[c] <= '9' && s[c] >= '0')
        {
            a[i].y *= 10;
            a[i].y += s[c] - '0';
            c++;
        }
        c++;
        while(s[c] <= '9' && s[c] >= '0' && c < 20)
        {
            a[i].p *= 10;
            a[i].p += s[c] - '0';
            c++;
        }

        //in >> a[i].x >> a[i].y >> a[i].p;
        a[i].poz = i;
    }

    sort(a + 1, a + n + 1, cmp);

    for(int i = 2; i <= NRMAX; i += 2)
        v[i]++;

    for(int i = 3; i <= NRMAX; i += 2)
        if(v[i] == 0)
        {
            for(int j = (i << 1); j <= NRMAX; j += i)
                v[j]++;
            v[i] = 1;
        }

    int curent = 1;
    for(int i = 0; i <= PMAX; i++)
    {
        int nr = 0;
        for(int j = 1; j <= NRMAX; j++)
            if(v[j] == i)
                d[++nr] = j;

        while(a[curent].p == i)
        {
            int x, y, xf, yf;
            x = a[curent].x;
            y = a[curent].y;
            int j, pas;

            j = 0, pas = (1 << 20);
            while(pas)
            {
                if(j + pas <= nr && d[j + pas] < x)
                    j += pas;
                pas >>= 1;
            }
            xf = j + 1;

            j = 0, pas = (1 << 20);
            while(pas)
            {
                if(j + pas <= nr && d[j + pas] <= y)
                    j += pas;
                pas >>= 1;
            }
            yf = j;

            rez[a[curent].poz] = yf - xf + 1;
            curent++;
        }
        /*for(int j = 1; j <= nr; j++)
            out << d[j] << ' ';
        out << '\n';*/
    }

    for(int i = 1; i <= n; i++)
        out << rez[i] << '\n';
    return 0;
}