import java.util.;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t–>0) {
int a = sc.nextInt();
int b = sc.nextInt();
boolean arr[] = new boolean[b+1];
for(int i=0;i<arr.length;i++) {
arr[i] = true;
}
long i;
for(i=2;ii<=b;i++) {
if(arr[(int)i]==true) {
for(long j=i*i;j<=b;j+=i) {
arr[(int)j]=false;
}
}
}
if(a==1)
i=2;
else
i=a;
int count=0;
for(;i<=b;i++) {
if(arr[(int)i]==true)
count++;
//System.out.println(i);
}
System.out.println(count);
}
}
}