object Main extends App {
  val scanner = new java.util.Scanner(System.in)

  val q = scanner.nextInt()

  val queries = (1 to q).map { _ =>
    (scanner.nextInt(), scanner.nextInt())
  }

  def prims(n: Int): Seq[Int] = {
    def sieve(xs: Seq[Int]): Seq[Int] = xs match {
      case Nil   => Nil
      case x+:xs => x +: sieve(xs.filter(_ % x != 0))
    }

    sieve((2 to n))
  }

  val max = queries.foldLeft(0) { (m, q) =>
    if(q._2 > m) q._2 else m
  }

  queries.map {
    case (l, r) =>
      val nums = l to r
      val ps = prims(r).toSeq
      nums.filter(n => ps.contains((n+1)/2) && ps.contains(n)).size
  }.foreach(println)
}
