fun main(args: Array<String>) {
    val Q = readLine()!!.toInt()
    val max = 100000
    val a = IntArray(max + 1)
    a.fill(0)
    val isPrime = eratosthenes(max)

    fun is2017Like(num: Int) : Boolean {
        return isPrime[num] && isPrime[(num +1) /2]
    }
    (1..max).forEach {
        a[it] = if (is2017Like(it)) 1 else 0
    }

    (0 until max).forEach {
        a[it+1] += a[it]
    }

    (1..Q).forEach {
        val (l, r) = readLine()!!.split(" ").map { it.toInt() }
        println(a[r] - a[l - 1])
    }
}

fun eratosthenes(N: Int) : BooleanArray {
    val isPrime = BooleanArray(N + 1)
    isPrime.fill(true)
    isPrime[0] = false
    isPrime[1] = false

    (2..N).forEach {
        if (isPrime[it]) {
            var i = 2
            while (i * it <= N) {
                isPrime[i*it] = false
                i++
            }
        }
    }

    return isPrime
}
