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 isPrim(n: Int): Boolean = {
    n >= 2 && (2 to scala.math.sqrt(n).toInt).iterator.forall(n % _ != 0)
  }

  def isSimilarTo2017(n: Int): Boolean =
    isPrim(n) && isPrim((n+1) / 2)

  queries.map {
    case (l, r) =>
      (l to r).iterator.filter(isSimilarTo2017).size
  }.foreach(println)
}
