import java.util.Scanner

case class Range(l: Int, r: Int) {
  val toList = l until r + 1
}


object Main {
  def read() = {
    val sc = new Scanner(System.in)
    val q = sc.nextInt()
    val ranges = for (_ <- 0 until q) yield Range(sc.nextInt(), sc.nextInt())
    (q, ranges)
  }

  def isPrime(n: Int): Boolean = {
    if (n <= 1) return false
    val notPrime = (2 until n - 1).exists(i => n % i == 0)
    return !notPrime
  }

  def like2017(n: Int): Boolean = isPrime(n) && isPrime((n + 1) / 2)

  def isOdd(n: Int) = n % 2 == 1

  def main(args: Array[String]): Unit = {
    val (q, ranges) = read()
    for (range <- ranges) {
      val xs = range.toList


      val result = xs.filter(isOdd).count(like2017)
      println(result)
    }
  }
}