import scala.io.{StdIn => in}

object Main extends App {
  val out = new java.io.PrintWriter(System.out)
  val n = 100000
  val prime = eratos(n)
  val table = Array.ofDim[Int](n+1)
  for(i <- 3 to n) {
    if(i % 2 == 1 && prime(i) && prime((i+1)/2)) {
      table(i) = table(i-1) + 1
    }
    else table(i) = table(i-1)
  }

  val q = in.readInt

  Iterator.continually(in.readLine)
    .take(q)
    .map(_.split(" ").map(_.toInt))
    .foreach(e => {
      val l = e(0)
      val r = e(1)
      out.println(table(r) - table(l-1))
    })
  out.flush
  
  def eratos(n:Int):Array[Boolean] = {
    val ret = Array.fill(n+1)(true)
    ret(0) = false
    ret(1) = false
    for(i <- 2 to n) {
      if(ret(i)) {
        var j = i + i
        while(j <= n) {
          ret(j) = false
          j += i
        }
      }
    }
    ret
  }
}