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 math
import sys

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False

q = input()
lr = []
max_num = 0
INF = sys.maxint
input_list = sieve_of_erastosthenes(100000)
# prime_list = [i for i, b in enumerate(input_list) if b == True]
prime_list_append = []
sum_count = 0
for index, i in enumerate(input_list):
    if i and input_list[(index + 1) / 2]:
        # print i, (index + 1)/2, sum_count
        sum_count += 1
        prime_list_append.append(sum_count)
    else:
        prime_list_append.append(sum_count)

for ii in xrange(q):
    tmp = map(int, raw_input().split(" "))
    # count = 0
    # for j in prime_list_append[tmp[0]:tmp[1]]:
    #     count += 1
    print prime_list_append[tmp[1]] - prime_list_append[tmp[0]-1]
