fun main(args: Array<String>) = yorukatsu14d()

fun yorukatsu14d() {
    val q = readLine()!!.toInt()
    val queries = (1..q).map {
        readLine()!!.split(' ').map { it.toInt() }.let { it[0] to it[1] }
    }

    val cSum = LongArray(100010)
    for (i in 3 until cSum.lastIndex) {
        cSum[i] = cSum[i - 1] +
                if (i % 2 != 0 && isPrime(i.toLong()) && isPrime((i + 1) / 2L)) 1 else 0
    }

    val answer = queries.map {
        val (left, right) = it
        cSum[right] - cSum[left - 1]
    }.joinToString(System.lineSeparator())

    println(answer)
}

private fun isPrime(n: Long): Boolean {
    val sqrt = Math.sqrt(n.toDouble()).toLong()
    for (i in 2..sqrt) if (n % i == 0L) return false
    return true
}
