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
  
  input_methods = ["clipboard", "file", "key"]
  using_method = 0
  input_method = input_methods[using_method]
  
  tin = lambda: map(int, input().split())
  lin = lambda: list(tin())
  mod = 1000000007
  
  # +++++
  
  
  def main():
      pp = [1] * (10**5 + 1)
      pp[0] = 0
      pp[1] = 0
      for i, _ in enumerate(pp):
          if pp[i] == 0:
              continue
          st = i
          while st * i < len(pp):
              pp[st * i] = 0
              st += 1
      like = pp[:]
      like[2] = 0
      for i, v in enumerate(pp):
  
          if v == 1 and i != 2 and pp[(i + 1) // 2] == 0:
              like[i] = 0
      ss = [0] * len(pp)
      for i, v in enumerate(ss[:-1]):
          ss[i + 1] = like[i + 1] + ss[i]
      # pa(like[:10])
      q = int(input())
      # b , c = tin()
      # s = input()
      for _ in range(q):
          l, r = tin()
          print(ss[r] - ss[l - 1])
  
  
  # +++++
  isTest = False
  
  
  def pa(v):
      if isTest:
          print(v)
  
  
  def input_clipboard():
      import clipboard
  
      input_text = clipboard.get()
      input_l = input_text.splitlines()
      for l in input_l:
          yield l
  
  
  if __name__ == "__main__":
      if sys.platform == "ios":
          if input_method == input_methods[0]:
              ic = input_clipboard()
              input = lambda: ic.__next__()
          elif input_method == input_methods[1]:
              sys.stdin = open("inputFile.txt")
          else:
              pass
          isTest = True
      else:
          pass
          # input = sys.stdin.readline
  
      ret = main()
      if ret is not None:
          print(ret)
  
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"}]