#include<iostream>
#include<vector>
using namespace std;
int prosti(int a,int b)
{
    vector<int> redica;
    redica.push_back(2);
    bool prosto = true;
    for(int i=2;i<=b;i++)
    {
        prosto = true;
        for(int j=0;j<redica.size();j++)
        {
            if(i%redica[j] == 0)
            {
                prosto = false;
                j = redica.size();
            }
        }
        if(prosto)
        {
            redica.push_back(i);
        }
    }
    int otg = 0;
    for(int i=0;i<redica.size();i++)
    {
        if(redica[i]>=a)
        {
            otg++;
        }
    }
    return otg;
}
int main()
{
    vector<int> otg;
    int a,b,k;
    cin>>k;
    for(int i=0;i<k;i++)
    {
        cin >> a >> b;
        otg.push_back(prosti(a,b));
    }
    for(int i=0;i<otg.size();i++)
    {
        cout<<otg[i]<<endl;
    }
}