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 math
  Q = int(input())#numの数の個数
  Query = []
  maxn=0
  for _ in range(Q):
      l,r = map(int,input().split())
      Query.append((l,r))
      maxn = max(maxn,r)
  N = maxn
  num = [0]*(N+2)#部分和を計算したい数列
  def souwa(left,right,ruisekiwa):#0based,numの[left,right)間の総和を計算
     return ruisekiwa[right]-ruisekiwa[left]
  def using_sqrt(N):#入力 対象の整数,出力,素数ならば1,合成数ならば1
      flag = 0
      for i in range(2,math.floor(math.sqrt(N))+1):
          if N % i == 0:
              flag = 1
              break
          else:
              continue
      if flag == 1:
          return 0
      else:
          return 1
  
  for i in range(1,N+2,2):
      if using_sqrt(i)==1 and using_sqrt((i+1)//2)==1:
          num[i] = 1
  ruisekiwa = [0]*(N+2)
  ruisekiwa[0] = 0
  num[1] =0
  for i in range(1,N+2):#累積和の前処理
      ruisekiwa[i]=num[i-1]+ruisekiwa[i-1]
  
  for q in Query:
      print(souwa(q[0],q[1]+1,ruisekiwa)
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"}]