object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val q = sc.nextInt()
  val lr = List.fill(q)((sc.nextInt()/2, sc.nextInt()/2))
  val m = 49999
  val isPrime = Array.fill(m+1)(true)
  isPrime(0) = false

  for (i <- 1 to m if isPrime(i)) {
    var k = 3
    while (((2*i + 1) * k) / 2 <= m) {
      isPrime(((2*i + 1) * k) / 2) = false
      k += 2
    }
  }

  val a = Array.tabulate(m+1){ i =>
    if (isPrime(i) && i % 2 == 0 && isPrime((i+1) / 2)) 1 else 0
  }
  a(1) = 1
  val b = a.scanLeft(0)(_+_)

  val pw = new java.io.PrintWriter(Console.out)
  for ((l, r) <- lr) {
    pw.println(b(r+1) - b(l))
  }
  pw.flush()
}
