We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

* 1≤Q≤10^5
* 1≤l_i≤r_i≤10^5
* l_i and r_i are odd.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


Q
l_1 r_1
:
l_Q r_Q


Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Examples

Input

1
3 7


Output

2


Input

4
13 13
7 11
7 11
2017 2017


Output

1
0
0
1


Input

6
1 53
13 91
37 55
19 51
73 91
13 49


Output

4
4
1
1
1
2
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	// write your code here
        final int size=99999;
        int[] numList=new int[size];
        boolean[] isPrimeList=new boolean[size];
        boolean[] simu2017List=new boolean[size];
        int[] cumuList=new int[size];
        for(int i=0;i<size;i++){
            numList[i]=i+2;
            isPrimeList[i]=true;
            simu2017List[i]=false;
        }
        for(int i=0;i<size;i++){
            int oriNum=i+2;
            if(isPrimeList[i]==true){
                for(int j=i+oriNum;j<size;j=j+oriNum){
                    isPrimeList[j]=false;
                }
            }
        }
        for(int i=0;i<size;i++){
            int oriNum=i+2;
            if(oriNum%2==0) continue;
            int index=(oriNum+1)/2-2;
            if(isPrimeList[i]){
                if(isPrimeList[index]){
                    simu2017List[i]=true;
                }
            }
        }
        cumuList[0]=0;
        for(int i=1;i<size;i++){
            cumuList[i]=simu2017List[i]?cumuList[i-1]+1:cumuList[i-1];
        }
/*
        System.out.println("numList");
        Arrays.stream(numList).forEach((a)->{
                System.out.print(a+" ");
        });
        System.out.println();
        System.out.println("isPrimeList");
        for(int i=0;i<isPrimeList.length;i++){
            System.out.print(isPrimeList[i]+" ");
        }
        System.out.println();
        System.out.println("simu2017List");
        for(int i=0;i<simu2017List.length;i++){
            System.out.print(simu2017List[i]+" ");
        }
        System.out.println();
        System.out.println("cumuList");
        Arrays.stream(cumuList).forEach((a)->{
            System.out.print(a+" ");
        });
        System.out.println();
*/

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        for(int i=0;i<n;i++){
            int l=scanner.nextInt();
            int r=scanner.nextInt();
            if(simu2017List[l==1?0:l-2]){
                System.out.println(cumuList[r-2]-cumuList[l==1?0:l-2]+1);
            }else{
                System.out.println(cumuList[r-2]-cumuList[l==1?0:l-2]);

            }
        }

    }
}
