import java.util.Scanner

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    val q = scanner.nextInt()

    val p = Array(100001, { i -> 0 } )
    p[0] = 0
    for (i in 1..100000) {
        if (isLike2017(i)) {
            p[i] = p[i - 1]+ 1
        } else {
            p[i] = p[i - 1]
        }
    }

    for (i in 1..q) {
        var l = scanner.nextInt()
        var r = scanner.nextInt()
        println(p[r] - p[l - 1])
    }
}

fun isPrime(n: Int): Boolean {
    if (n <= 1) return false
    if (n <= 3) return true
    for (i in 2..(n - 1)) {
        if (n % i == 0) return false
        if (i * i > n) return true
    }
    return true
}

fun isLike2017(n: Int): Boolean {
    return n % 2 == 1 && isPrime(n) && isPrime((n + 1) / 2)
}