#include <bits/stdc++.h>
#define N int(1e6+1)
using namespace std;
int nt[N], c[N];
void sangnt()
{
    fill(nt+1,nt+N+1,1);
    fill(c+1,c+N+1,1);
    nt[1] = c[1] = 0;
    for (int i=2; i*i<=N; i++)
    if (nt[i]==1)
        for (int j=i*i; j<=N; j+=i)
            nt[j] = c[j] = 0;
}
int demuoc(int x)
{
    int souoc = 1, i = 2;
    while (i*i <= x)
    {
        int d = 0;
        while (x % i == 0)
        {
            d++;
            x = x/i;
        }
        souoc *= 2*d + 1;
        i++;
    }
    if (x > 1) souoc *= 3;
    return souoc;
}
void init()
{
    sangnt();
    for (int i=2; i*i<=N; i++)
    {
        int k = demuoc(i);
        if (nt[k])
            c[i*i] = 1;
    }
    for (int i=1; i<=N; i++)
        c[i] += c[i-1];
}
int main()
{
    freopen("uocnto.inp","r",stdin);
    freopen("uocnto.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    init();
    int t;
    cin >> t;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        cout << c[b] - c[a-1] << '\n';
    }
    return 0;
}