def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す

    isprime=[1]*(n+1)

    isprime[0]=0

    isprime[1]=0

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

        if not isprime[i]:

            continue

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

            isprime[j]=0

    return isprime



max_n=100000

isprime=get_isPrime(max_n)



ruiseki=[]

for i in range(max_n+1):

    if i==0 or i==1 or i==2:

        ruiseki.append(0)

    else:

        if i%2==0:

            ruiseki.append(ruiseki[i-1])

        else:

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

                ruiseki.append(ruiseki[i-1]+1)

            else:

                ruiseki.append(ruiseki[i-1])



q=int(eval(input()))

for _ in range(q):

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

    print((ruiseki[right]-ruiseki[left-1]))
from itertools import chain, accumulate





def prime_set(N):

    """

    Nまでの素数のsetを返す

    """

    if N < 4:

        return ({}, {}, {2}, {2, 3})[N]

    Nsq = int(N ** 0.5 + 0.5) + 1

    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))

    for i in range(5, Nsq, 2):

        if i in primes:

            primes -= set(range(i * i, N + 1, i * 2))

    return primes





U = 10 ** 5 + 10

primes = prime_set(U)

memo = [0] * U

for i in range(1, U, 2):

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

        memo[i] = 1

memo = list(accumulate(memo))



Q = int(input())

ans = []

for _ in range(Q):

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

    ans.append(memo[r] - memo[l - 1])

print(*ans, sep="\n")

def get_isPrime(n):  # 1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime = [1] * (n + 1)
    isprime[0] = 0
    isprime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not isprime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            isprime[j] = 0
    return isprime


max_n = 100000
isprime = get_isPrime(max_n)
ruiseki = []
for i in range(max_n + 1):
    if i == 0 or i == 1 or i == 2:
        ruiseki.append(0)
    else:
        if i % 2 == 0:
            ruiseki.append(ruiseki[i - 1])
        else:
            if isprime[i] and isprime[int((i + 1) / 2)]:
                ruiseki.append(ruiseki[i - 1] + 1)
            else:
                ruiseki.append(ruiseki[i - 1])
q = int(eval(input()))
for _ in range(q):
    left, right = list(map(int, input().split()))
    print((ruiseki[right] - ruiseki[left - 1]))

from itertools import chain, accumulate


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N**0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


U = 10**5 + 10
primes = prime_set(U)
memo = [0] * U
for i in range(1, U, 2):
    if i in primes and (i + 1) // 2 in primes:
        memo[i] = 1
memo = list(accumulate(memo))
Q = int(input())
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(memo[r] - memo[l - 1])
print(*ans, sep="\n")

-def get_isPrime(n):  # 1~nまでの数で、素数は1、それ以外は0となるようなリストを返す -    isprime = [1] * (n + 1) -    isprime[0] = 0 -    isprime[1] = 0 -    for i in range(2, int(n**0.5) + 1): -        if not isprime[i]: -            continue -        for j in range(i * 2, n + 1, i): -            isprime[j] = 0 -    return isprime +from itertools import chain, accumulate -max_n = 100000 -isprime = get_isPrime(max_n) -ruiseki = [] -for i in range(max_n + 1): -    if i == 0 or i == 1 or i == 2: -        ruiseki.append(0) -    else: -        if i % 2 == 0: -            ruiseki.append(ruiseki[i - 1]) -        else: -            if isprime[i] and isprime[int((i + 1) / 2)]: -                ruiseki.append(ruiseki[i - 1] + 1) -            else: -                ruiseki.append(ruiseki[i - 1]) -q = int(eval(input())) -for _ in range(q): -    left, right = list(map(int, input().split())) -    print((ruiseki[right] - ruiseki[left - 1])) +def prime_set(N): +    """ +    Nまでの素数のsetを返す +    """ +    if N < 4: +        return ({}, {}, {2}, {2, 3})[N] +    Nsq = int(N**0.5 + 0.5) + 1 +    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6))) +    for i in range(5, Nsq, 2): +        if i in primes: +            primes -= set(range(i * i, N + 1, i * 2)) +    return primes + + +U = 10**5 + 10 +primes = prime_set(U) +memo = [0] * U +for i in range(1, U, 2): +    if i in primes and (i + 1) // 2 in primes: +        memo[i] = 1 +memo = list(accumulate(memo)) +Q = int(input()) +ans = [] +for _ in range(Q): +    l, r = map(int, input().split()) +    ans.append(memo[r] - memo[l - 1]) +print(*ans, sep="\n")