package TIMECOMPLEXITY;
import java.util.Arrays;
import java.util.Scanner;
public class SIEVEOFERATOSTHENIS {
public static void main(String[] args) {
Scanner scn =new Scanner(System.in);
int T=scn.nextInt();
int s1,s2;
while(T>0) {
s1=scn.nextInt();
s2=scn.nextInt();
primevisits(s1,s2);
T--;
}
}
public static void primevisits(int s1,int s2) {
boolean [] primes =new boolean[s2+1];
Arrays.fill(primes,true);
primes[0]=primes[1]=false;
for (int table=2;table *table<=s2;table++) {
if (primes[table]==false) {
continue;
}
for(int multi=2;table *multi<=s2;multi++) {
primes[table *multi]=false;
}
}
int count=0;
for(int i=0;i<primes.length;i++) {
if (primes[i]==true) {
count++;
}
}
System.out.println(count);
}
}