def main():

    from itertools import accumulate



    def Eratosthenes(x: int) -> set:

        from math import sqrt

        sup = int(x)

        primes = {i for i in range(2, sup+1)}

        for i in range(2, int(sqrt(sup+1))+1):

            if i in primes:

                mul = 2

                while i*mul <= sup:

                    primes.discard(i*mul)

                    mul += 1

        return primes

    P = Eratosthenes(10**5+5)

    A = [0]*(10**5+5)

    for i in range(3, 10**5+5):

        if i in P and (i+1)//2 in P:

            A[i] += 1

    S = list(accumulate(A))



    Q = int(eval(input()))

    LR = [[int(i) for i in input().split()] for j in range(Q)]

    for le, ri in LR:

        print((S[ri] - S[le-1]))





if __name__ == '__main__':

    main()

def Eratosthenes(x: int) -> set:

    from math import sqrt

    sup = int(x)

    primes = {i for i in range(2, sup+1)}

    for i in range(2, int(sqrt(sup+1))+1):

        if i in primes:

            mul = 2

            while i*mul <= sup:

                primes.discard(i*mul)

                mul += 1

    return primes





def main():

    import sys

    input = sys.stdin.buffer.readline

    P = Eratosthenes(10**5+5)

    A = [0]*(10**5+5)

    for i in range(3, 10**5+5):

        if i in P and (i+1)//2 in P:

            A[i] = 1

    from itertools import accumulate

    S = list(accumulate(A))

    Q = int(eval(input()))

    LR = [[int(i) for i in input().split()] for j in range(Q)]

    for le, ri in LR:

        print((S[ri] - S[le-1]))





if __name__ == '__main__':

    main()

def main():
    from itertools import accumulate

    def Eratosthenes(x: int) -> set:
        from math import sqrt

        sup = int(x)
        primes = {i for i in range(2, sup + 1)}
        for i in range(2, int(sqrt(sup + 1)) + 1):
            if i in primes:
                mul = 2
                while i * mul <= sup:
                    primes.discard(i * mul)
                    mul += 1
        return primes

    P = Eratosthenes(10**5 + 5)
    A = [0] * (10**5 + 5)
    for i in range(3, 10**5 + 5):
        if i in P and (i + 1) // 2 in P:
            A[i] += 1
    S = list(accumulate(A))
    Q = int(eval(input()))
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    for le, ri in LR:
        print((S[ri] - S[le - 1]))


if __name__ == "__main__":
    main()

def Eratosthenes(x: int) -> set:
    from math import sqrt

    sup = int(x)
    primes = {i for i in range(2, sup + 1)}
    for i in range(2, int(sqrt(sup + 1)) + 1):
        if i in primes:
            mul = 2
            while i * mul <= sup:
                primes.discard(i * mul)
                mul += 1
    return primes


def main():
    import sys

    input = sys.stdin.buffer.readline
    P = Eratosthenes(10**5 + 5)
    A = [0] * (10**5 + 5)
    for i in range(3, 10**5 + 5):
        if i in P and (i + 1) // 2 in P:
            A[i] = 1
    from itertools import accumulate

    S = list(accumulate(A))
    Q = int(eval(input()))
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    for le, ri in LR:
        print((S[ri] - S[le - 1]))


if __name__ == "__main__":
    main()

+def Eratosthenes(x: int) -> set: +    from math import sqrt + +    sup = int(x) +    primes = {i for i in range(2, sup + 1)} +    for i in range(2, int(sqrt(sup + 1)) + 1): +        if i in primes: +            mul = 2 +            while i * mul <= sup: +                primes.discard(i * mul) +                mul += 1 +    return primes + + -    from itertools import accumulate +    import sys -    def Eratosthenes(x: int) -> set: -        from math import sqrt - -        sup = int(x) -        primes = {i for i in range(2, sup + 1)} -        for i in range(2, int(sqrt(sup + 1)) + 1): -            if i in primes: -                mul = 2 -                while i * mul <= sup: -                    primes.discard(i * mul) -                    mul += 1 -        return primes - +    input = sys.stdin.buffer.readline -            A[i] += 1 +            A[i] = 1 +    from itertools import accumulate +