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.Math.*;
import java.math.BigInteger;

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[] result = new int[100001];
		Prime p = new Prime(100001);
		for(int i = 1; i < result.length; i++){
		    if(i != 2 && p.isPrime(i) && p.isPrime((i+1)/2)){
		        result[i] += result[i-1] + 1;
		    }else{
		        result[i] += result[i-1];
		    }
		}
		
		// 出力
		for(int i = 0; i < q; i++){
		    System.out.println(result[r[i]] - result[l[i]-1]);
		}
	}
}

class Prime {
    int n;
    ArrayList<Integer> primes;
    int[] seive;
    
    public Prime(int n){
        this.n = n;
        int[] seive = new int[n+1];
        Arrays.fill(seive, -1);
        ArrayList<Integer> primes = new ArrayList<Integer>();
        for(int i = 2; i <= n; i++){
            if(seive[i] != -1) continue;
            primes.add(i);
            seive[i] = i;
            for(long j = (long)i*i; j <= n; j += i){
                if(seive[(int)j] == -1) seive[(int)j] = i; 
            }
        }
        this.seive = seive;
        this.primes = primes;
    }
    
    public boolean isPrime(int x){
        return seive[x] == x;
    }
    
    public HashMap<Integer, Integer> factorization(int x){
        HashMap<Integer, Integer> factorization = new HashMap<Integer, Integer>();
        ArrayList<Integer> factorList = factorList(x);
        if(factorList.size() == 0) return factorization;
        for(Integer i : factorList){
            int cnt = factorization.getOrDefault(i, 0);
            factorization.put(i, cnt + 1);
        }
        return factorization;
    }
    
    private ArrayList<Integer> factorList(int x){
        ArrayList<Integer> factorList = new ArrayList<Integer>();
        while(x != 1){
            factorList.add(seive[x]);
            x /= seive[x];
        }
        return factorList;
    }
    
    public HashMap<Integer, Integer> lcmMap(int[] array){
        HashMap<Integer, Integer> lcmMap = new HashMap<Integer, Integer>();
		for(int i = 0; i < array.length; i++){
		    HashMap<Integer, Integer> map = factorization(array[i]);
		    for(Integer key : map.keySet()){
		        lcmMap.put(key, max(lcmMap.getOrDefault(key, 0), map.get(key)));
		    }
		}
        return lcmMap;
    }
    
}


