#include <iostream>
using namespace std;
bool mas[ 1000000 ] = { 0 };
void pr()
{
    mas[ 1 ] = 1;
    for(int j = 2; j <= 1000000; j ++ )
    {
        if( mas[ j ] == 0 )
          for( int i = j * 2; i <= 1000000; i += j)
               mas[ i ] = 1;
    }
}
int main()
{
    pr();
    long long k, a, b;
    cin >> k;
    long long br[ 1000 ] = { 0 };
    for(int i = 0; i < k; i ++ )
    {
        cin >> a >> b;
        for(int j = a; j <= b; j ++ )
        {
            if( mas[ j ] == 0 )
              br[ i ] ++;
        }
    }
    for(int i = 0; i < k; i ++ )
       cout << br[ i ] << "\n";
    return 0;
}