import math

q = int(eval(input()))

l = []

r = []

for i in range(q):

    li, ri = list(map(int, input().split()))

    l.append(li)

    r.append(ri)



r_max = max(r) + 10

is_prime = [True] * (r_max+1)

is_prime[0] = is_prime[1] = False

for i in range(2, r_max):

    if is_prime[i]:

        for j in range(2, r_max // i + 1):

            is_prime[i*j] = False



# print(is_prime)

a = [0] * r_max

for i in range(3, r_max):

    a[i] = a[i-1]

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

        a[i] += 1

# print(a)



for i in range(q):

    print((a[r[i]] - a[l[i]-1]))

import sys

import math

input = sys.stdin.readline





def eratosthenes(n):

    is_prime = [True] * (n + 1)

    is_prime[0] = is_prime[1] = False

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

        if is_prime[i]:

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

                is_prime[i * j] = False

    return is_prime





q = int(eval(input()))

l = []

r = []

for i in range(q):

    li, ri = list(map(int, input().split()))

    l.append(li)

    r.append(ri)



r_max = max(r)

is_prime = eratosthenes(r_max)

a = [0] * (r_max + 1)

for i in range(3, r_max + 1):

    a[i] = a[i - 1]

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

        a[i] += 1

# print(a)



for i in range(q):

    print((a[r[i]] - a[l[i] - 1]))

import math

q = int(eval(input()))
l = []
r = []
for i in range(q):
    li, ri = list(map(int, input().split()))
    l.append(li)
    r.append(ri)
r_max = max(r) + 10
is_prime = [True] * (r_max + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, r_max // i + 1):
            is_prime[i * j] = False
# print(is_prime)
a = [0] * r_max
for i in range(3, r_max):
    a[i] = a[i - 1]
    if is_prime[i] and is_prime[(i + 1) // 2]:
        a[i] += 1
# print(a)
for i in range(q):
    print((a[r[i]] - a[l[i] - 1]))

import sys
import math

input = sys.stdin.readline


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


q = int(eval(input()))
l = []
r = []
for i in range(q):
    li, ri = list(map(int, input().split()))
    l.append(li)
    r.append(ri)
r_max = max(r)
is_prime = eratosthenes(r_max)
a = [0] * (r_max + 1)
for i in range(3, r_max + 1):
    a[i] = a[i - 1]
    if is_prime[i] and is_prime[(i + 1) // 2]:
        a[i] += 1
# print(a)
for i in range(q):
    print((a[r[i]] - a[l[i] - 1]))

+import sys + +input = sys.stdin.readline + + +def eratosthenes(n): +    is_prime = [True] * (n + 1) +    is_prime[0] = is_prime[1] = False +    for i in range(2, n // 2 + 1): +        if is_prime[i]: +            for j in range(2, n // i + 1): +                is_prime[i * j] = False +    return is_prime + -r_max = max(r) + 10 -is_prime = [True] * (r_max + 1) -is_prime[0] = is_prime[1] = False -for i in range(2, r_max): -    if is_prime[i]: -        for j in range(2, r_max // i + 1): -            is_prime[i * j] = False -# print(is_prime) -a = [0] * r_max -for i in range(3, r_max): +r_max = max(r) +is_prime = eratosthenes(r_max) +a = [0] * (r_max + 1) +for i in range(3, r_max + 1):