#include <iostream>
#include <cmath>

using namespace std;

int pricnt[1000005];
bool comp[1000005];

bool prime(int a)
{
    int ogr = sqrt(a) + 1;
    for(int i=2;i < ogr;i++)if(a%i == 0)return false;
    return true;
}

void Evklid()
{
    int k=1, i;
    comp[0] = comp[1] = true;
    while(true)
    {
        k++;
        for(i=k;i < 1000002;i++)if(comp[i] == false)break;
        k = i;
        if(k == 1000002)return;
        for(i = 2*k;i < 1000002;i+=k)comp[i] = true;
    }
}

void generate()
{
    int count = 0;
    Evklid();
    
    for(int i=0;i <1000002;i++)
    {
        if(comp[i] == false)count++;
        pricnt[i] = count;
    }
}
int main()
{
    int awns[1005];
    int k, a, b;
    generate();

    cin >> k;
    for(int i=0;i < k;i++)
    {
        cin >> a >> b;
        awns[i] = pricnt[b] - pricnt[a-1];
    }
    for(int i=0;i < k;i++)cout << awns[i] << endl;
    return 0;
}