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: from itertools import takewhile
  
  """
  演算子は要素とセットでモノイドを形成するようなものでなければならない。
  すなわち、結合律が成り立ち単位元が存在する必要がある。
  
  equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
  """
  
  
  class SegmentTree:
  
      @classmethod
      def all_identity(cls, operator, equality, identity, size):
          return cls(
              operator, equality, identity, [identity] * (2 << (size - 1).bit_length())
          )
  
      @classmethod
      def from_initial_data(cls, operator, equality, identity, data):
          size = 1 << (len(data) - 1).bit_length()
          temp = [identity] * (2 * size)
          temp[size : size + len(data)] = data
          data = temp
  
          for i in reversed(range(size)):
              data[i] = operator(data[2 * i], data[2 * i + 1])
          return cls(operator, equality, identity, data)
  
      # これ使わずファクトリーメソッド使いましょうね
      def __init__(self, operator, equality, identity, data):
          if equality is None:
              equality = lambda a, b: False
          self.op = operator
          self.eq = equality
          self.id = identity
          self.data = data
          self.size = len(data) // 2
  
      def _interval(self, a, b):
          a += self.size
          b += self.size
          ra = self.id
          rb = self.id
  
          data = self.data
          op = self.op
          while a < b:
              if a & 1:
                  ra = op(ra, data[a])
                  a += 1
              if b & 1:
                  b -= 1
                  rb = op(data[b], rb)
              a >>= 1
              b >>= 1
          return op(ra, rb)
  
      def __getitem__(self, i):
          if isinstance(i, slice):
              return self._interval(
                  0 if i.start is None else i.start,
                  self.size if i.stop is None else i.stop,
              )
          elif isinstance(i, int):
              return self.data[i + self.size]
  
      def __setitem__(self, i, v):
          i += self.size
          data = self.data
          op = self.op
          eq = self.eq
          while i and not eq(data[i], v):
              data[i] = v
              v = op(data[i ^ 1], v) if i & 1 else op(v, data[i ^ 1])
              i >>= 1
  
      def __iter__(self):
          return self.data[self.size :]
  
  
  # 素数生成器
  def generate_primes():
      from collections import defaultdict
      from itertools import count
  
      D = defaultdict(list)
  
      q = 2
      for q in count(2):
          if q in D:
              for p in D[q]:
                  D[p + q].append(p)
              del D[q]
          else:
              yield q
              D[q * q].append(q)
  
  
  from operator import add, eq
  
  Q = int(input())
  Q = [tuple(map(int, input().split())) for _ in range(Q)]
  
  m = max(r for l, r in Q)
  
  
  primes = set(takewhile(lambda x: x <= m, generate_primes()))
  primes.remove(2)
  
  A = [0] * (m + 1)
  
  for p in primes:
      if (p + 1) // 2 in primes:
          A[p] = 1
  
  A[3] = 1
  
  T = SegmentTree.from_initial_data(add, eq, 0, A)
  
  for l, r in Q:
      print(T[l : r + 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"}]