#include<iostream>
#define w 1000010
using namespace std;
bool r[w];
int main()
{
    long long k,a,b,v,br;
    cin>>k;
    for (int i=0; i<k; i++)
    {
        cin>>a>>b;
        br=0;
        for (int j=a; j<=b; j++)
        {
            v=0;
            if (j==1)
                continue;
            if (r[j]==1)
            {
                br++;
                continue;
            }
            for (int f=2; f*f<=j; f++)
                if (j%f==0)
                {
                    v=1;
                    break;
                }
            if (v==0)
            {
                br++;
                r[j]=1;
            }
        }
        cout<<br<<endl;
    }
    return 0;
}