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: import sys
  
  ## io
  IS = lambda: sys.stdin.readline().rstrip()
  II = lambda: int(IS())
  MII = lambda: list(map(int, IS().split()))
  MIIZ = lambda: list(map(lambda x: x - 1, MII()))
  ## dp
  INIT_VAL = 0
  MD2 = lambda d1, d2: [[INIT_VAL] * d2 for _ in range(d1)]
  MD3 = lambda d1, d2, d3: [MD2(d2, d3) for _ in range(d1)]
  ## math
  DIVC = lambda x, y: -(-x // y)
  DIVF = lambda x, y: x // y
  from itertools import accumulate as acc
  
  
  class PrimeOptimizer:
      def __init__(self, MAX_NUM=10**3):
          """MAX_NUM以下の素数テーブルを生成する。
          生成した素数テーブルはprime_factorizationで使用する。
          """
          is_prime = [True] * MAX_NUM
          is_prime[0] = False
          is_prime[1] = False
          primes = []
          for i in range(MAX_NUM):
              if is_prime[i]:
                  primes.append(i)
                  for j in range(2 * i, MAX_NUM, i):
                      is_prime[j] = False
          self.primes = primes
  
      def prime_factorization(self, x):
          """xを素因数分解する。
          分解先の素数はself.primesを利用する。
          @param x (int): 分解対象の正整数
          @return res (dict): key = 素数、value = 素数の数で構成される辞書
          """
          res = {}
          for prime in self.primes:
              while x % prime == 0:
                  if not prime in res:
                      res[prime] = 0
                  res[prime] += 1
                  x //= prime
          if x > 1:
              res[x] = 1
          return res
  
  
  def main():
      q = II()
      lr = [MII() for _ in range(q)]
      pm = PrimeOptimizer(MAX_NUM=10**5)
      prims = set(pm.primes)
      like_2017 = [0] * 10**5
      for n in range(1, 10**5):
          if n in prims and (n + 1) // 2 in prims:
              like_2017[n] = 1
      acc_like_2017 = list(acc(like_2017))
      for l, r in lr:
          print(acc_like_2017[r] - acc_like_2017[l - 1])
  
  
  if __name__ == "__main__":
      main()
  
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"}]