def sieve(N):#エラトステネスの篩

    prime = [0]*(N+1)

    isprime = [True]*(N+1)

    isprime[0]=isprime[1] = False

    num = 0

    for p in range(2,N+1):

        if isprime[p]:

            prime[num] = p

            num += 1

            for j in range(2*p,N+1,p):

                isprime[j] = False

    return prime

from bisect import bisect_left as bl

from bisect import bisect_right as br

lis = sieve(10**5)

prime = set(lis)-{0}

for i in range(len(lis)):

    if lis[i] != 0:

        if (lis[i]+1)//2 in prime:continue

        else:lis[i] = 0

    else:continue

Q = int(eval(input()))

lis = set(lis)-{0}

lis = sorted(tuple(lis))

for _ in range(Q):

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

    t = bl(lis,l)

    s = br(lis,r)

    tmp = s-t

    print(tmp)



def sieve(N):#エラトステネスの篩

    prime = [0]*(N+1)

    isprime = [True]*(N+1)

    isprime[0]=isprime[1] = False

    num = 0

    for p in range(2,N+1):

        if isprime[p]:

            prime[num] = p

            num += 1

            for j in range(2*p,N+1,p):

                isprime[j] = False

    return prime



lis = sieve(10**5)

prime = set(lis)-{0}

for i in range(len(lis)):

    if lis[i] != 0:

        if (lis[i]+1)//2 in prime:continue

        else:lis[i] = 0

    else:continue

Q = int(eval(input()))

lis = set(lis)-{0}

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

for i in range(10**5):

    if i+1 in lis:

        c[i+1] = c[i]+1

    else:

        c[i+1] =c[i]

c = tuple(c)

for _ in range(Q):

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

    tmp = c[r]-c[l-1]

    print(tmp)



def sieve(N):  # エラトステネスの篩
    prime = [0] * (N + 1)
    isprime = [True] * (N + 1)
    isprime[0] = isprime[1] = False
    num = 0
    for p in range(2, N + 1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2 * p, N + 1, p):
                isprime[j] = False
    return prime


from bisect import bisect_left as bl
from bisect import bisect_right as br

lis = sieve(10**5)
prime = set(lis) - {0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i] + 1) // 2 in prime:
            continue
        else:
            lis[i] = 0
    else:
        continue
Q = int(eval(input()))
lis = set(lis) - {0}
lis = sorted(tuple(lis))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    t = bl(lis, l)
    s = br(lis, r)
    tmp = s - t
    print(tmp)

def sieve(N):  # エラトステネスの篩
    prime = [0] * (N + 1)
    isprime = [True] * (N + 1)
    isprime[0] = isprime[1] = False
    num = 0
    for p in range(2, N + 1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2 * p, N + 1, p):
                isprime[j] = False
    return prime


lis = sieve(10**5)
prime = set(lis) - {0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i] + 1) // 2 in prime:
            continue
        else:
            lis[i] = 0
    else:
        continue
Q = int(eval(input()))
lis = set(lis) - {0}
c = [0] * (10**5 + 1)
for i in range(10**5):
    if i + 1 in lis:
        c[i + 1] = c[i] + 1
    else:
        c[i + 1] = c[i]
c = tuple(c)
for _ in range(Q):
    l, r = list(map(int, input().split()))
    tmp = c[r] - c[l - 1]
    print(tmp)

-from bisect import bisect_left as bl -from bisect import bisect_right as br - -lis = sorted(tuple(lis)) +c = [0] * (10**5 + 1) +for i in range(10**5): +    if i + 1 in lis: +        c[i + 1] = c[i] + 1 +    else: +        c[i + 1] = c[i] +c = tuple(c) -    t = bl(lis, l) -    s = br(lis, r) -    tmp = s - t +    tmp = c[r] - c[l - 1]