#include<bits/stdc++.h>
using namespace std;
#define MAXVAL 1000000
vector v(MAXVAL+6 , 0);
vector findSieve(long long int n){
v[0] = v[1] = 0;
v[2] = 1;
for(long long int i=3;i<MAXVAL;i+=2){
v[i]=1;
}
for(long long int i=3;i<MAXVAL;i+=2){
if(v[i]==1){
for(long long int j = i*i ; j<MAXVAL;j+=i){
v[j] = 0;
}
}
}
vector prime(1,0);
long long int count=0;
for(long long int i=1;i<=n;i++){
if(v[i]==1){
count++;
//cout<<i<<" "<<count<<endl;
}
prime.push_back(count);
}
//cout<<endl;
//for(auto a: prime)
return prime;
}
int main(){
int t;
cin>>t;
vector<pair<long long int,long long int>> values;
long long int max =0;
vector<long long int> prime;
for(int i=0;i<t;i++){
long long int val1,val2;
cin>>val1>>val2;
values.push_back(make_pair(val1,val2));
max=(max<val2)?val2:max;
}
prime=findSieve(max);
for(auto c:values){
int a = prime[c.second];
//cout<<a<<endl<<endl;
cout<<prime[c.second]-prime[c.first-1] <<endl;
}
return 0;
}
