//when i am taking multab<=1000002 in second for loop inside prime function , it is not print //anything
import java.util.;
public class Main {
public static void prime(boolean arr[]){
Arrays.fill(arr,true);
arr[0]=false;
arr[1]=false;
for(int tab=2;tab*tab<=1000002;tab++){
if(arr[tab]){
for(int mul=2;mul*tab<1000002;mul++){
arr[tab*mul]=false;
}
}
}
//return arr;
}
public static void main(String args[]) {
try{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
boolean arr[]= new boolean[1000002];
// arr=prime(arr);
prime(arr);
while(n-->0){
int a=sc.nextInt();
int b=sc.nextInt();
int count=0;
for(int i=a;i<=b;i++){
if(arr[i])
count++;
}
//System.out.println("HELLO");
System.out.println(count);
}
}
catch(Exception e ){
}
}
}