from itertools import accumulate

Q = int(eval(input()))



def prime(n):

    # 素数列挙

    # nまでの素数をリストで返す(nを含む)

    primes = set(range(2, n+1))

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

        primes.difference_update(list(range(i*2, n+1, i)))

    primes=list(primes)

    return primes



prime_set = set(prime(10**5))

ans = []



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

    if i%2 == 0:

        ans.append(0)

    else:

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

            ans.append(1)

        else:

            ans.append(0)

ans = list(accumulate(ans))



for i in range(Q):

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

    print((ans[r] - ans[l-1]))
from itertools import accumulate

Q = int(eval(input()))

m = 0

ls = []

for i in range(Q):

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

    m = max(m, max(l, r))

    ls.append((l, r))



def sieve_eratosthenes(n):

    primes = [0, 1] * (n // 2 + 1)

    if n % 2 == 0:

        primes.pop()

    primes[1] = 0

    primes[2] = 1

    for p in range(3, n + 1, 2):

        if primes[p]:

            for q in range(p * p, n + 1, 2 * p):

                primes[q] = 0

    return primes



a = sieve_eratosthenes(m)

b = [0 for i in range(m+1)]

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

    if i%2 == 1 and a[i] == 1 and a[(i+1)//2] == 1:

        b[i] = 1

c = list(accumulate(b))

for l, r in ls:

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

from itertools import accumulate

Q = int(eval(input()))


def prime(n):
    # 素数列挙
    # nまでの素数をリストで返す(nを含む)
    primes = set(range(2, n + 1))
    for i in range(2, int(n**0.5 + 1)):
        primes.difference_update(list(range(i * 2, n + 1, i)))
    primes = list(primes)
    return primes


prime_set = set(prime(10**5))
ans = []
for i in range(10**5 + 1):
    if i % 2 == 0:
        ans.append(0)
    else:
        if i in prime_set and (i + 1) // 2 in prime_set:
            ans.append(1)
        else:
            ans.append(0)
ans = list(accumulate(ans))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((ans[r] - ans[l - 1]))

from itertools import accumulate

Q = int(eval(input()))
m = 0
ls = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    m = max(m, max(l, r))
    ls.append((l, r))


def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes


a = sieve_eratosthenes(m)
b = [0 for i in range(m + 1)]
for i in range(2, m + 1):
    if i % 2 == 1 and a[i] == 1 and a[(i + 1) // 2] == 1:
        b[i] = 1
c = list(accumulate(b))
for l, r in ls:
    print((c[r] - c[l - 1]))

+m = 0 +ls = [] +for i in range(Q): +    l, r = list(map(int, input().split())) +    m = max(m, max(l, r)) +    ls.append((l, r)) -def prime(n): -    # 素数列挙 -    # nまでの素数をリストで返す(nを含む) -    primes = set(range(2, n + 1)) -    for i in range(2, int(n**0.5 + 1)): -        primes.difference_update(list(range(i * 2, n + 1, i))) -    primes = list(primes) +def sieve_eratosthenes(n): +    primes = [0, 1] * (n // 2 + 1) +    if n % 2 == 0: +        primes.pop() +    primes[1] = 0 +    primes[2] = 1 +    for p in range(3, n + 1, 2): +        if primes[p]: +            for q in range(p * p, n + 1, 2 * p): +                primes[q] = 0 -prime_set = set(prime(10**5)) -ans = [] -for i in range(10**5 + 1): -    if i % 2 == 0: -        ans.append(0) -    else: -        if i in prime_set and (i + 1) // 2 in prime_set: -            ans.append(1) -        else: -            ans.append(0) -ans = list(accumulate(ans)) -for i in range(Q): -    l, r = list(map(int, input().split())) -    print((ans[r] - ans[l - 1])) +a = sieve_eratosthenes(m) +b = [0 for i in range(m + 1)] +for i in range(2, m + 1): +    if i % 2 == 1 and a[i] == 1 and a[(i + 1) // 2] == 1: +        b[i] = 1 +c = list(accumulate(b)) +for l, r in ls: +    print((c[r] - c[l - 1]))