import java.util.*;
public class Main {
public static void main(String args[]){
int a,b;
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int p[]=new int[n];
Arrays.fill(p,0);
primesieve(p,n);
int csum[]=new int[n];
Arrays.fill(csum,0);
for(int i=1;i<=n;i++){
csum[i]=csum[i-1]+p[i];
}
while(n-->=0){
a=sc.nextInt(); b=sc.nextInt();
int sum=csum[b]-csum[a-1];
System.out.print(sum);
System.out.println();
}}
public static void primesieve(int[] p,int n){
for(int i=3;i<=n;i+=2){
p[i]=1;
for(i=3;i<=n;i+=2)
{
if(p[i]==1)
{
for(int j=i*i;j<=n;j=j+i)
p[j]=0;
}
}
p[2]=1;
p[1]=p[0]=0;
}
}
}