#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std ;

typedef long long ll ;

bool prime[] ;

bool prime1[] ;

int main()

{

    int t ;

    scanf("%d",&t) ;

    while(t--)

    {

        ll a,b ;

        scanf("%lld%lld",&a,&b) ;

        for(ll i= ;i*i<=b ;i++)prime[i]=true ;

        for(ll i= ;i<=b-a ;i++)prime1[i]=true ;

        for(ll i= ;i*i<=b ;i++)

        {

            if(prime[i])

            {

                for(ll j=*i ;j*j<=b ;j+=i)prime[j]=false ;

                for(ll j=max(2LL,(a+i-)/i)*i ;j<=b ;j+=i)prime1[j-a]=false ;

            }

        }

        int ans= ;

        for(ll i= ;i<=b-a ;i++)

            if(prime1[i])ans++ ;

        if(a==)ans-- ;

        printf("%d\n",ans) ;

    }

    return  ;

}