
import java.util.Arrays

fun main(args: Array<String>) {
    val numbers = (1..100000 step 2)
            .filter { isPrime(it) && isPrime((it + 1) / 2) }

    val q = readLine()!!.toInt()
    for (i in 1..q) {
        val (l, r) = readLine()!!.split(" ").map(String::toInt)
        val count = count(numbers, r) - count(numbers, l - 1)
        println(count)
    }
}

fun isPrime(x: Int): Boolean {
    if (x == 1) return false
    for (k in 2..x) {
        if (k * k > x) {
            break
        }
        if (x % k == 0) {
            return false
        }
    }
    return true
}

fun count(numbers: List<Int>, x: Int): Int {
    val returnValue = numbers.binarySearch(x)
    return if (returnValue >= 0) {
        returnValue + 1
    } else {
        -returnValue - 1
    }
}
