fun main(arg: Array<String>) {
    val MAX = 100001
    val isPrime = Array(MAX) { true }
    isPrime[0] = false; isPrime[1] = false
    for (i in 2 until MAX) {
        if (!isPrime[i]) continue
        for (j in i * 2 until MAX step i) isPrime[j] = false
    }
    val a = IntArray(MAX)
    for (i in 0 until MAX) {
        if (i % 2 == 0) continue
        if (isPrime[i] && isPrime[(i + 1) / 2]) a[i] = 1
    }
    val s = IntArray(MAX + 1)
    for (i in 0 until MAX) s[i + 1] = s[i] + a[i]
    val Q = nextInt()
    val ans = IntArray(Q)
    repeat(Q) { q ->
        var (l, r) = listOfInt()
        ans[q] = s[r + 1] - s[l]
    }
    println(ans.joinToString("\n"))
}
fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }
