def gen_is_prime(n):

    is_prime = [True] * (n + 1)

    is_prime[0] = False

    is_prime[1] = False

    for i in range(2, n + 1):

        for j in range(i * 2, n + 1, i):

            is_prime[j] = False

    # return [i for i in range(n + 1) if is_prime[i]]

    return is_prime





if __name__ == "__main__":

    max_n = 10 ** 5

    is_prime = gen_is_prime(max_n)



    is_like_2017 = [False] * (max_n + 1)

    for i in range(max_n + 1):

        if is_prime[i] and is_prime[(i + 1) // 2]:

            is_like_2017[i] = True



    sum_is_like_2017 = [0] * (max_n + 2)

    for i in range(max_n + 1):

        sum_is_like_2017[i + 1] = sum_is_like_2017[i] + is_like_2017[i]



    q = int(eval(input()))

    lr = [list(map(int, input().split())) for _ in range(q)]

    for l, r in lr:

        print((sum_is_like_2017[r + 1] - sum_is_like_2017[l]))

from itertools import accumulate





def gen_primes(n: int) -> set:

    if n < 2:

        return set()

    is_prime = [True] * n

    for i in range(3, n, 2):

        if is_prime[i]:

            is_prime[i * i:: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)

    return {2} | {i for i in range(3, n, 2) if is_prime[i]}





if __name__ == "__main__":

    max_n = 10 ** 5 + 1

    primes = gen_primes(max_n)



    is_like_2017 = [True if i in primes and (i + 1) // 2 in primes else False for i in range(max_n)]

    sum_is_like_2017 = tuple(accumulate(is_like_2017))



    q = int(eval(input()))

    lr = [list(map(int, input().split())) for _ in range(q)]

    for l, r in lr:

        print((sum_is_like_2017[r] - sum_is_like_2017[l - 1]))

def gen_is_prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    # return [i for i in range(n + 1) if is_prime[i]]
    return is_prime


if __name__ == "__main__":
    max_n = 10**5
    is_prime = gen_is_prime(max_n)
    is_like_2017 = [False] * (max_n + 1)
    for i in range(max_n + 1):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            is_like_2017[i] = True
    sum_is_like_2017 = [0] * (max_n + 2)
    for i in range(max_n + 1):
        sum_is_like_2017[i + 1] = sum_is_like_2017[i] + is_like_2017[i]
    q = int(eval(input()))
    lr = [list(map(int, input().split())) for _ in range(q)]
    for l, r in lr:
        print((sum_is_like_2017[r + 1] - sum_is_like_2017[l]))

from itertools import accumulate


def gen_primes(n: int) -> set:
    if n < 2:
        return set()
    is_prime = [True] * n
    for i in range(3, n, 2):
        if is_prime[i]:
            is_prime[i * i :: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if is_prime[i]}


if __name__ == "__main__":
    max_n = 10**5 + 1
    primes = gen_primes(max_n)
    is_like_2017 = [
        True if i in primes and (i + 1) // 2 in primes else False for i in range(max_n)
    ]
    sum_is_like_2017 = tuple(accumulate(is_like_2017))
    q = int(eval(input()))
    lr = [list(map(int, input().split())) for _ in range(q)]
    for l, r in lr:
        print((sum_is_like_2017[r] - sum_is_like_2017[l - 1]))

-def gen_is_prime(n): -    is_prime = [True] * (n + 1) -    is_prime[0] = False -    is_prime[1] = False -    for i in range(2, n + 1): -        for j in range(i * 2, n + 1, i): -            is_prime[j] = False -    # return [i for i in range(n + 1) if is_prime[i]] -    return is_prime +from itertools import accumulate + + +def gen_primes(n: int) -> set: +    if n < 2: +        return set() +    is_prime = [True] * n +    for i in range(3, n, 2): +        if is_prime[i]: +            is_prime[i * i :: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1) +    return {2} | {i for i in range(3, n, 2) if is_prime[i]} -    max_n = 10**5 -    is_prime = gen_is_prime(max_n) -    is_like_2017 = [False] * (max_n + 1) -    for i in range(max_n + 1): -        if is_prime[i] and is_prime[(i + 1) // 2]: -            is_like_2017[i] = True -    sum_is_like_2017 = [0] * (max_n + 2) -    for i in range(max_n + 1): -        sum_is_like_2017[i + 1] = sum_is_like_2017[i] + is_like_2017[i] +    max_n = 10**5 + 1 +    primes = gen_primes(max_n) +    is_like_2017 = [ +        True if i in primes and (i + 1) // 2 in primes else False for i in range(max_n) +    ] +    sum_is_like_2017 = tuple(accumulate(is_like_2017)) -        print((sum_is_like_2017[r + 1] - sum_is_like_2017[l])) +        print((sum_is_like_2017[r] - sum_is_like_2017[l - 1]))