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
from pprint import pprint as pp
def GI(): return int(raw_input())
def GIS(): return map(int, raw_input().split())

from math import sqrt
from itertools import izip

N = 10 ** 5

def main():
  primes = get_primes()
  n_p1_2 = [primes[(i+1)/2] for i in xrange(1, N+1)]
  n_p1_2[2] = 0

  s = 0
  c = []
  for p, n in izip(primes, n_p1_2):
    s += (p and n)
    c.append(s)

  #for i in xrange(0, 54):
  #  print i, ' - ', c[i], primes[i], n_p1_2[i]

  for _ in xrange(GI()):
    l, r = GIS()
    print c[r] - c[l-1]

def get_primes():
  a = [1] * (N + 1)
  a[0] = a[1] = 0

  for i in xrange(2, int(sqrt(N))):
    if not a[i]:
      continue
    for j in xrange(i ** 2, N+1, i):
      a[j] = 0

  return a

main()