output_description: Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th
  query.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      Q
      l_1 r_1
      :
      l_Q r_Q
attempt: def eratosthenes(N):
      prime = []
      a = list(range(2, N + 1))
      end = N**0.5
      while len(a) and a[0] <= end:
          nn = a.pop(0)
          prime.append(nn)
          a = [i for i in a if i % nn != 0]
      prime += a
      return prime
  
  
  def binsearch_lb(lst, lb):
      """lb以上の最小のインデックス"""
      li = 0
      ri = len(lst) - 1
      if lst[li] >= lb:
          return 0
      if lst[ri] < lb:
          return -1
      while li + 1 < ri:
          tgt = (li + ri) // 2
          if lst[tgt] < lb:
              li = tgt
          else:
              ri = tgt
      return ri
  
  
  def binsearch_ub(lst, ub):
      """ub以下の最大のインデックス"""
      li = 0
      ri = len(lst) - 1
      if lst[li] > ub:
          return -1
      if lst[ri] <= ub:
          return ri
      while li + 1 < ri:
          tgt = (li + ri) // 2
          if lst[tgt] > ub:
              ri = tgt
          else:
              li = tgt
      return li
  
  
  N = int(input().strip())
  primes = sorted(eratosthenes(int(1e5)))
  p_set = set(primes)
  primes2 = []
  for p in primes:  # MlogM
      if (p + 1) // 2 in p_set:
          primes2.append(p)
  for i in range(N):  # N
      l, r = map(int, input().split())
      li = binsearch_lb(primes2, l)  # l以上のインデックス logM
      ri = binsearch_ub(primes2, r)  # r以下のインデックス
      print(ri - li + 1)
  
problem_description: Statement
  
  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.
samples: [{"input": "1\n    3 7", "output": "2\n    \n\n  * 3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.\n  * 5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.\n  * 7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.\n\nThus, the response to the first query should be 2.\n\n* * *"}, {"input": "4\n    13 13\n    7 11\n    7 11\n    2017 2017", "output": "1\n    0\n    0\n    1\n    \n\nNote that 2017 is also similar to 2017.\n\n* * *"}, {"input": "6\n    1 53\n    13 91\n    37 55\n    19 51\n    73 91\n    13 49", "output": "4\n    4\n    1\n    1\n    1\n    2"}]