import java.io.{BufferedReader, InputStream, InputStreamReader}
import java.util.{Comparator, StringTokenizer}

import scala.collection.mutable
import scala.util.Sorting
import math.{abs, max, min}
import scala.collection.mutable.{ArrayBuffer, ListBuffer}

object Main {
  val MOD = 1000000007
  def solve(): Unit = {
    val sc = new InputReader(System.in)
    val Q = sc.nextInt()

    val N = 100000
    val p = Array.fill[Int](N + 1)(1)
    p(0) = 0
    p(1) = 0
    val d = Array.ofDim[Int](N + 1)

    (2 to math.sqrt(N).toInt) foreach { i =>
      if (p(i) == 1) {
        (2 until N / i) foreach { j =>
          p(j * i) = 0
        }
      }
    }

    (1 to N).reverse foreach { i =>
      if (p(i) == 1 && p((i + 1) / 2) == 1) d(i) = 1
    }

    (0 until N) foreach { i =>
      d(i + 1) += d(i)
    }

    (0 until Q) foreach { _ =>
      val l, r = sc.nextInt()
      println(d(r) - d(l - 1))
    }
  }


  def main(args: Array[String]): Unit = {
    solve()
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = null

    def next: String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next.toInt
    def nextLong(): Long = next.toLong
    def nextChar(): Char = next.charAt(0)
  }

}
