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.*;

class Main {
   public static void main(String[] args)
   {
      Scanner scan = new Scanner(System.in);
      int     n    = Integer.parseInt(scan.next());

      final int MAX = 100000 + 1;

      int[] count = new int[MAX];
      count[0] = count[1] = count[2] = 0;
      boolean[] primes = new boolean[MAX];

      primes[2] = true;

      for(int i = 3; i < MAX; i += 2){
          primes[i] = true;
          }

      for(int i = 3; i * i < MAX; i += 2){
          if(primes[i]){
             for(int j = i * 2; j < MAX; j += i){
                 primes[j] = false;
                 }
             }
          }
      for(int i = 3; i < MAX; i++){
          if(primes[i] == true){
             if(primes[(i + 1) / 2] == true){
                count[i] = count[i - 1] + 1;
                }
             else{
                 primes[(i + 1) / 2] = false;
                 count[i]            = count[i - 1];
                 }
             }
          else{
              count[i] = count[i - 1];
              }
          }
      //System.out.println(count);

      for(int i = 0; i < n; i++){
          int a   = Integer.parseInt(scan.next());
          int b   = Integer.parseInt(scan.next());
          int cou = 0;

          if(a == b){
             cou = count[a] - count[a - 1];
             System.out.println(cou);
             }
          else{
              cou = count[b] - count[a - 1];
              System.out.println(cou);
              }
          }
   }
}
