import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int[] primes = new int[1000001];
soe(primes);
int[] cumsum = new int[1000001];
for(int i=1 ; i<=1000000 ; i++) {
cumsum[i] = cumsum[i-1]+primes[i];
}
int q = sc.nextInt();
while(q-->0) {
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println(cumsum[b]-cumsum[a-1]);
}
}
public static void soe(int[] primes) {
Arrays.fill(primes, 1);
primes[0] = 0;
primes[1] = 0;
for (int table = 2; table * table <= 1000000; table++) {
int j = 2;
while (table * j <= 1000000) {
primes[table * j] = 0;
j++;
}
}
}
}