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

import static java.lang.System.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int Q = sc.nextInt();

        int[] l = new int[Q];
        int[] r = new int[Q];
        for (int i = 0; i < Q; i++) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
        }

        int NUM = 100001;
        List<Integer> primes = sieveOfEratosthenes(NUM);

        boolean[] isPrime = new boolean[NUM];
        for (int p : primes) {
            isPrime[p] = true;
        }

        int[] cnt = new int[NUM];
        for (int i = 0; i < cnt.length; i++) {
            if (isPrime[i] && (i + 1) % 2 == 0 && isPrime[(i + 1) / 2]) {
                cnt[i]++;
            }
        }

        for (int i = 1; i < cnt.length; i++) {
            cnt[i] += cnt[i - 1];
        }

        for (int i = 0; i < Q; i++) {
            out.println(cnt[r[i]] - cnt[l[i] - 1]);
        }
    }


    public static List<Integer> sieveOfEratosthenes(int max) {
        List<Integer> primes = new ArrayList<Integer>();

        int prime;
        int max_check = (int) Math.floor(Math.sqrt(max));   //ふるい落としのチェックに利用する値
        List<Integer> nums = new ArrayList<Integer>();     //素数候補
        for (int i = 2; i <= max; i++) {
            nums.add(i);
        }


        while (true) {
            // ふるい落とした先頭は素数
            if (nums.size() < 2) {
                break;
            }
            prime = nums.get(0);

            // ふるい落としのチェックに利用する値は最大値の平方根未満の最大値
            if (prime >= max_check) {
                break;
            }

            primes.add(prime);

            // primeでふるい落とし
            List<Integer> rest_nums = new ArrayList<Integer>();
            for (int n : nums) {
                if (n % prime != 0) {
                    rest_nums.add(n);
                }
            }

            // ふるい落とした候補に更新
            nums = rest_nums;
        }

        //残っている候補は素数
        for (int n : nums) {
            primes.add(n);
        }

        return primes;
    }

}