fun main(args: Array<String>) {
    val c= readLine()!!.toInt()
    val array= mutableListOf<List<Int>>()
    for(i in 0 until c){
        val array2= readLine()!!.split(" ").map { it.toInt() }
        array.add(array2)
    }
    val pl=Array(100001,{true})
    pl[0]=false
    pl[1]=false
    for(i in 2..100000){
        if(pl[i]){
            for(j in i+i..100000 step i){
                pl[j]=false
            }
        }
    }
    val pl2=Array(100001,{0})
    var count=0
    for(i in 3..100000){
        if(pl[i]&&pl[(i+1)/2])count++
        pl2[i]=count
    }
    for(i in array){
        var k= pl2[i[1]]-pl2[i[0]]
        if(pl2[i[0]]>pl2[i[0]-1])k++
        println(k)
    }
}