import java.io.*
import java.util.*
import java.lang.*
import java.lang.Math.*


fun sievePrimes(N: Int): BooleanArray {
    if (N <= 1) return BooleanArray(N+1){false}
    var fc = IntArray(N+1){0}
    fc[0] = -1
    fc[1] = -1
    for (i in 2..N) {
        if (fc[i] != 0) continue
        fc[i] = i
        for(j in i*2..N step i) {
            if (fc[j] == 0) fc[j] = i
        }
    }
    var isPrime = BooleanArray(N+1){false}
    for (i in 2..N) {
        if (fc[i] == i) isPrime[i] = true
    }
    return isPrime
}

class CumSum(val A: LongArray) {
    private var csum: LongArray = LongArray(A.size + 1){0L}
    init {
        for (i in 1..A.size) {
            this.csum[i] = this.csum[i-1] + A[i-1]
        }
    }
    fun sum(L: Int, R: Int): Long {
        val r = min(R, A.size);
        val l = max(L, 0)
        if (l >= r) return 0
        return this.csum[r] - this.csum[l];
    }
}

fun solve() {
    val Q = rd.readInt()
    val L = IntArray(Q); val R = IntArray(Q)
    for (q in 0 until Q) {
        val (l, r) = rd.readIntArray()
        L[q] = l; R[q] = r
    }

    val NMAX = 100_000
    val isPrime = sievePrimes(NMAX)
    val isTarget = LongArray(NMAX+1){0L}
    for (i in 3 .. NMAX) {
        if (isPrime[i] && isPrime[(i+1)/2]) {
            isTarget[i] = 1L
        }
    }

    val csum = CumSum(isTarget)

    for (q in 0 until Q) {
        val ans = csum.sum(L[q], R[q]+1)
        println(ans)
    }
}


//val rd = debug.Reader("abc", "084", "d", "sample-1")
val rd = Reader()


fun main(args: Array<String>) {
    try {
        var exception: Throwable? = null
        val sth = Thread(null, SolveThread(), "solveThread", 128 * 1024 * 1024)
        sth.setUncaughtExceptionHandler { _, e -> exception = e }
        sth.start(); sth.join()
        if (exception != null) throw exception!!
    } catch (e: Exception) { throw e }
}
const val MOD = 1_000_000_007L; const val INF = Int.MAX_VALUE/2; const val LINF = Long.MAX_VALUE/2
val EPS = 1e-9; fun DBLEQ(a: Double, b: Double): Boolean {return abs(a - b) < EPS}
data class IntPair(val first: Int, val second: Int)
data class To(val idx: Int, val cost: Long)
fun <T>edge(V: Int): Array<ArrayList<T>> { return Array(V){ArrayList<T>()} }
val errPrintln: (Any) -> Unit = { msg -> System.err.println(msg) }
fun rAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("EAssert Error: $msg"); throw Error(msg) }
}
fun tAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("TAssert Error: $msg"); Thread.sleep(3000) }
}
class SolveThread : Runnable {
    override fun run() { solve() }
}
class Reader {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    val readString: () -> String = { br.readLine() }
    val readInt: () -> Int = { br.readLine().toInt() }
    val readLong: () -> Long = { br.readLine().toLong() }
    val readIntArray: () -> IntArray = { br.readLine().split(' ').map { it.toInt() }.toIntArray() }
    val readLongArray: () -> LongArray = { br.readLine().split(' ').map { it.toLong() }.toLongArray() }
    val readListInt: () -> List<Int> = { br.readLine().split(' ').map { it.toInt() } }
    val readListLong: () -> List<Long> = { br.readLine().split(' ').map { it.toLong() } }
}


Measured memory_bytes: 61056