from itertools import accumulate

Q = int(eval(input()))



def sieve(n):

    if n == 0:

        return [False]



    is_prime = [True] * (n + 1)

    is_prime[0] = False

    is_prime[1] = False

    

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

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

            is_prime[j] = False

                

    return is_prime



MAX = 10 ** 5

is_prime = sieve(MAX)

cnt = [0] * (MAX + 1)

for i in range(MAX + 1):

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

        cnt[i] = 1

cnt = list(accumulate(cnt))



for _ in range(Q):

    l, r = list(map(int, input().split()))

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

Q = int(eval(input()))

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



n = 10 ** 5 + 2

is_prime = [True] * (n + 1)

is_prime[0] = False

is_prime[1] = False



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

    if not is_prime[i]:

        continue



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

        is_prime[j] = False



like = [False] * (n + 1)

for i in range(n):

    like[i] = is_prime[i] and is_prime[(i + 1) // 2]



cumsum = [0] * (n + 1)

for i in range(n):

    cumsum[i + 1] = cumsum[i] + like[i]



for l, r in X:

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

from itertools import accumulate

Q = int(eval(input()))


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


MAX = 10**5
is_prime = sieve(MAX)
cnt = [0] * (MAX + 1)
for i in range(MAX + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        cnt[i] = 1
cnt = list(accumulate(cnt))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cnt[r] - cnt[l - 1]))

Q = int(eval(input()))
X = [list(map(int, input().split())) for _ in range(Q)]
n = 10**5 + 2
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, n + 1):
    if not is_prime[i]:
        continue
    for j in range(2 * i, n + 1, i):
        is_prime[j] = False
like = [False] * (n + 1)
for i in range(n):
    like[i] = is_prime[i] and is_prime[(i + 1) // 2]
cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i + 1] = cumsum[i] + like[i]
for l, r in X:
    print((cumsum[r + 1] - cumsum[l]))

-from itertools import accumulate - - - -def sieve(n): -    if n == 0: -        return [False] -    is_prime = [True] * (n + 1) -    is_prime[0] = False -    is_prime[1] = False -    for i in range(2, n + 1): -        for j in range(2 * i, n + 1, i): -            is_prime[j] = False -    return is_prime - - -MAX = 10**5 -is_prime = sieve(MAX) -cnt = [0] * (MAX + 1) -for i in range(MAX + 1): -    if is_prime[i] and is_prime[(i + 1) // 2]: -        cnt[i] = 1 -cnt = list(accumulate(cnt)) -for _ in range(Q): -    l, r = list(map(int, input().split())) -    print((cnt[r] - cnt[l - 1])) +X = [list(map(int, input().split())) for _ in range(Q)] +n = 10**5 + 2 +is_prime = [True] * (n + 1) +is_prime[0] = False +is_prime[1] = False +for i in range(2, n + 1): +    if not is_prime[i]: +        continue +    for j in range(2 * i, n + 1, i): +        is_prime[j] = False +like = [False] * (n + 1) +for i in range(n): +    like[i] = is_prime[i] and is_prime[(i + 1) // 2] +cumsum = [0] * (n + 1) +for i in range(n): +    cumsum[i + 1] = cumsum[i] + like[i] +for l, r in X: +    print((cumsum[r + 1] - cumsum[l]))