import java.util.*;
public class Main {
public static Scanner scn = new Scanner(System.in);
public static void main(String args[]) {
int n = scn.nextInt();
for(int i=0; i<n; i++)
{
int a = scn.nextInt();
int b = scn.nextInt();
nOfPrime(a,b);
}
}
public static void nOfPrime(int a, int b)
{
int count=0;
for(int i=a; i<=b; i++)
{
boolean flag = true;
if(i==1)
flag = false;
for(int j=2; j*j<=i; j++)
{
if(i%j==0)
{
flag = false;
break;
}
}
if(flag==true)
count++;
}
System.out.println(count);
}
}