import java.util.*;
public class primevisits {
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
int n,flag;
n=sc.nextInt();
int [][] arr= new int [n][2];
for(int i=0;i<n;i++) {
for(int j=0;j<2;j++) {
arr[i][j]=sc.nextInt();
}
}
for(int i=0;i<n;i++) {
int counter=0;
int a = arr[i][0];
int b = arr[i][1];
for(int k=a;k<=b;k++) {
if(k==1 || k==0) {
continue;
}
flag=1;
for(int j=2;j<=k/2;++j) {
if(k%j==0) {
flag=0;
break;
}
}
if(flag==1)
counter++;
}
System.out.println(counter);
}
}
}