def is_prime(num):

    if num == 1:

        return False

    limit = int(num ** 0.5) + 1

    for i in range(2, limit):

        if num % i == 0:

            return False

    return True





cumsum = [0] * (10**5 + 2)



count = 0

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

    if is_prime(num):

        if is_prime((num+1)//2):

            count += 1



    cumsum[num] = count

    cumsum[num+1] = count



q = int(eval(input()))

for i in range(q):

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

    res = cumsum[right] - cumsum[left-1]

    print(res)
primes = set(range(3, 10**5, 2))

primes.add(2)

cumsum = [0] * (10**5 + 2)



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

    if i in primes:

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

            primes.discard(not_prime)





count = 0

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

    if num in primes:

        if (num+1)//2 in primes:

            count += 1



    cumsum[num] = count

    cumsum[num+1] = count



q = int(eval(input()))

for i in range(q):

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

    res = cumsum[right] - cumsum[left-1]

    print(res)
def is_prime(num):
    if num == 1:
        return False
    limit = int(num**0.5) + 1
    for i in range(2, limit):
        if num % i == 0:
            return False
    return True


cumsum = [0] * (10**5 + 2)
count = 0
for num in range(1, 10**5, 2):
    if is_prime(num):
        if is_prime((num + 1) // 2):
            count += 1
    cumsum[num] = count
    cumsum[num + 1] = count
q = int(eval(input()))
for i in range(q):
    left, right = list(map(int, input().split()))
    res = cumsum[right] - cumsum[left - 1]
    print(res)

primes = set(range(3, 10**5, 2))
primes.add(2)
cumsum = [0] * (10**5 + 2)
for i in range(3, 10**5):
    if i in primes:
        for not_prime in range(i + i, 10**5, i):
            primes.discard(not_prime)
count = 0
for num in range(1, 10**5, 2):
    if num in primes:
        if (num + 1) // 2 in primes:
            count += 1
    cumsum[num] = count
    cumsum[num + 1] = count
q = int(eval(input()))
for i in range(q):
    left, right = list(map(int, input().split()))
    res = cumsum[right] - cumsum[left - 1]
    print(res)

-def is_prime(num): -    if num == 1: -        return False -    limit = int(num**0.5) + 1 -    for i in range(2, limit): -        if num % i == 0: -            return False -    return True - - +primes = set(range(3, 10**5, 2)) +primes.add(2) +for i in range(3, 10**5): +    if i in primes: +        for not_prime in range(i + i, 10**5, i): +            primes.discard(not_prime) -    if is_prime(num): -        if is_prime((num + 1) // 2): +    if num in primes: +        if (num + 1) // 2 in primes: