Q = int(eval(input()))

is_prime = {i:True for i in range(10**5+1)}

is_prime[0], is_prime[1] = False, False

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

    if is_prime[i]:

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

            is_prime[j] = False

s = [0] * (10**5+1)

for i in range(1, 10**5):

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

for _ in range(Q):

    left, right = list(map(int, input().split()))

    print((s[right+1]-s[left]))
Q = int(eval(input()))

is_prime = [True for i in range(10**5+1)]

is_prime[0], is_prime[1] = False, False

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

    if is_prime[i]:

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

            is_prime[j] = False

s = [0] * (10**5+1)

for i in range(1, 10**5):

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

for _ in range(Q):

    left, right = list(map(int, input().split()))

    print((s[right+1]-s[left]))
Q = int(eval(input()))
is_prime = {i: True for i in range(10**5 + 1)}
is_prime[0], is_prime[1] = False, False
for i in range(2, 10**5 + 1):
    if is_prime[i]:
        for j in range(i * 2, 10**5 + 1, i):
            is_prime[j] = False
s = [0] * (10**5 + 1)
for i in range(1, 10**5):
    s[i + 1] = s[i] + int(is_prime[i] and is_prime[(i + 1) // 2])
for _ in range(Q):
    left, right = list(map(int, input().split()))
    print((s[right + 1] - s[left]))

Q = int(eval(input()))
is_prime = [True for i in range(10**5 + 1)]
is_prime[0], is_prime[1] = False, False
for i in range(2, 10**5 + 1):
    if is_prime[i]:
        for j in range(i * 2, 10**5 + 1, i):
            is_prime[j] = False
s = [0] * (10**5 + 1)
for i in range(1, 10**5):
    s[i + 1] = s[i] + int(is_prime[i] and is_prime[(i + 1) // 2])
for _ in range(Q):
    left, right = list(map(int, input().split()))
    print((s[right + 1] - s[left]))

-is_prime = {i: True for i in range(10**5 + 1)} +is_prime = [True for i in range(10**5 + 1)]