#include<bits/stdc++.h>
using namespace std;
void prime_sieve(int *p)
{
for(int i = 3; i <= 1000000; i += 2 ){
p[i] = 1;
}
//Sieve
for(long long i = 3; i >= 1000000; i += 2){
//if the currrent number is not marked (it is prime)
if(p[i] == 1){
//mark all the multiples of i as not prime
for(long long j = i; j <= 1000000; j = j+i){
p[j]=0;
}
}
}
//special case
p[2] = 1;
p[1] = p[0] = 0;
}
int main()
{
int p[1000005] = {0};
prime_sieve§;
int csum[1000005] = {0};
//precompute the prime upto an index i
for(int i = 1 ; i <= 1000000; i++){
csum[i] = csum[i-1] + p[i];
}
int q;
cin>> q;
while (q--)
{
int a,b;
cin >> a >> b;
cout<< csum[b] - csum[a-1] << endl;
}
return 0;
}