import kotlin.math.sqrt

fun intList() = readLine()?.split(" ")?.map(String::toInt) ?: TODO()
fun main(args: Array<String>) {
    val q = readLine()?.toInt() ?: return
    val likes = Array(100000 + 2) { 0 }
    var p = 0
    var prime = generatePrime(p)
    var i = 1
    var count = 0
    while (i <= 100000) {
        val diff = prime * 2 - i
        when {
            diff < 0 -> {
                p++
                prime = generatePrime(p)
            }
            else -> {
                if (diff == 1L && isPrime(i.toLong())) {
                    count++
                }
                likes[i] = count
                likes[i + 1] = count
                i += 2
            }
        }
    }
    buildString {
        repeat(q) {
            val (l, r) = intList()
            appendln(likes[r] - likes[l - 1])
        }
    }.let {
        println(it.trimIndent())
    }
}

val memo = hashMapOf<Int, Long>()
fun generatePrime(index: Int): Long {
    if (index == 0) {
        return 2
    }
    if (index == 1) {
        return 3
    }
    memo[index]?.let {
        return it
    }
    val prev = generatePrime(index - 1)
    var next = prev + 2
    var i = 0
    var prime = 0L
    var l = sqrt(next.toDouble()).toLong()
    while (i < index - 1 && l >= prime) {
        prime = generatePrime(i++)
        if (next % prime == 0L) {
            next += 2
            i = 1
            l = sqrt(next.toDouble()).toLong()
        }
    }
    memo[index] = next
    return next
}

fun isPrime(candidate: Long): Boolean {
    var i = 0
    var prime = 0L
    val l = sqrt(candidate.toDouble()).toLong()
    while (l > prime) {
        prime = generatePrime(i++)
        if (candidate % prime == 0L) {
            return false
        }
    }
    return true
}
