def eratosthenes(limit):

    A = [i for i in range(2, limit+1)]

    P = []

    time = 0

    while True:

        prime = min(A)

        if prime > 316: break

        P.append(prime)

        i = 0

        while i < len(A):

            if A[i] % prime == 0:

                A.pop(i)

                continue

            i += 1

    for a in A: P.append(a)

    return P

l = eratosthenes(10**5)

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

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

for i in l: d[i] += 1

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

    ans[i] += ans[i-1]

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

for _ in range(int(eval(input()))):

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

    print((ans[r]-ans[l-1]))
def primes(n):

    ass = []

    is_prime = [True] * (n + 1)

    is_prime[0] = False

    is_prime[1] = False

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

        if not is_prime[i]: continue

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

            is_prime[j] = False

    for i in range(len(is_prime)):

        if is_prime[i]: ass.append(i)

    return ass

d, ans = [0]*(10**5+1), [0]*(10**5+1)

for i in primes(10**5): d[i] += 1

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

    ans[i] += ans[i-1]

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

for _ in range(int(eval(input()))):

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

    print((ans[r]-ans[l-1]))
def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > 316:
            break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        P.append(a)
    return P


l = eratosthenes(10**5)
ans = [0] * (10**5 + 1)
d = [0] * (10**5 + 1)
for i in l:
    d[i] += 1
for i in range(2, 10**5 + 1):
    ans[i] += ans[i - 1]
    if i % 2 == 1 and d[i] and d[(i + 1) // 2]:
        ans[i] += 1
for _ in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    print((ans[r] - ans[l - 1]))

def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


d, ans = [0] * (10**5 + 1), [0] * (10**5 + 1)
for i in primes(10**5):
    d[i] += 1
for i in range(2, 10**5 + 1):
    ans[i] += ans[i - 1]
    if i % 2 == 1 and d[i] and d[(i + 1) // 2]:
        ans[i] += 1
for _ in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    print((ans[r] - ans[l - 1]))

-def eratosthenes(limit): -    A = [i for i in range(2, limit + 1)] -    P = [] -    time = 0 -    while True: -        prime = min(A) -        if prime > 316: -            break -        P.append(prime) -        i = 0 -        while i < len(A): -            if A[i] % prime == 0: -                A.pop(i) -                continue -            i += 1 -    for a in A: -        P.append(a) -    return P +def primes(n): +    ass = [] +    is_prime = [True] * (n + 1) +    is_prime[0] = False +    is_prime[1] = False +    for i in range(2, int(n**0.5) + 1): +        if not is_prime[i]: +            continue +        for j in range(i * 2, n + 1, i): +            is_prime[j] = False +    for i in range(len(is_prime)): +        if is_prime[i]: +            ass.append(i) +    return ass -l = eratosthenes(10**5) -ans = [0] * (10**5 + 1) -d = [0] * (10**5 + 1) -for i in l: +d, ans = [0] * (10**5 + 1), [0] * (10**5 + 1) +for i in primes(10**5):