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
prime = [True]*(10**5+1)
prime[0] = False
prime[1] = False

for a in range(2,318): # >>> gmpy2.isqrt(10**5+1) -> mpz(316)
  if prime[a] == False:
    continue
  else:
    for b in range(a*2,10**5+1,a): 
      prime[b] = False
"""
print prime
import gmpy2

for a in range(0,10**5+1):
  if prime[a] != gmpy2.is_prime(a):
    print "NO"
    print a
"""
ans = [0]*(10**5+1)
now = 0
for a in range(3,10**5+1,2):
  if prime[a] == True and prime[(a+1)/2] == True:
    now = now + 1
  ans[a] = now

q = int(raw_input())
for a in range(q):
  l,r = map(int,raw_input().split(" "))
  x = ans[r] - ans[l]
  if prime[l] == True and prime[(l+1)/2] == True:
    x = x + 1
  print x
