#include<bits/stdc++.h>
using namespace std;
int m[80000],kk=0,h,a,b;
int main()
{
    for(int i=2;i<=1000000;i++)
    {
        int f=0;
        for(int j=2;j*j<=i;j++)
            if(i%j==0)
            {
                f=1;
                break;
            }
        if(f==0)
        {
            kk++;
            m[kk]=i;
        }
    }
    int k,u=0;
    cin>>k;
    while(u<k)
    {
        u++;
        scanf("%d%d",&a,&b);
        h=1;
        while(m[h]<a&&h<=kk)
        {
            if(m[h+1000]<a&&h+1000<=kk)h+=1000;
            else h++;
        }
        int hh=h;
        h=1;
        while(m[h]<b&&h<=kk)
        {
            if(m[h+1000]<b&&h+1000<=kk)h+=1000;
            else h++;
        }
        if(m[h]!=b)h--;
        if(h<hh||h==hh)
        {
            if(h<hh)cout<<0<<endl;
            else cout<<1<<endl;
            continue;
        }
        cout<<h-hh+1<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int m[1500000],kk=0,h,a,b;
int main()
{
    for(int i=2;i<=1000000;i++)
    {
        int f=0;
        for(int j=2;j*j<=i;j++)
            if(i%j==0)
            {
                f=1;
                break;
            }
        if(f==0)
        {
            kk++;
            m[kk]=i;
        }
    }
    int k,u=0;
    cin>>k;
    while(u<k)
    {
        u++;
        cin>>a>>b;
        h=1;
        while(m[h]<a&&h<=kk)
        {
            if(m[h+1000]<a&&h+1000<=kk)h+=1000;
            else h++;
        }
        int hh=h;
        h=1;
        while(m[h]<b&&h<=kk)
        {
            if(m[h+1000]<b&&h+1000<=kk)h+=1000;
            else h++;
        }
        if(m[h]!=b)h--;
        if(h<hh||h==hh)
        {
            if(h<hh)cout<<0<<endl;
            else cout<<1<<endl;
            continue;
        }
        cout<<h-hh+1<<endl;
    }
    return 0;
}