def sb(n):

    arr = []

    temp = n

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

        if temp%i==0:

            cnt=0

            while temp%i==0:

                cnt+=1

                temp //= i

            arr.append([i, cnt])

    if temp!=1:

        arr.append([temp, 1])

    if arr==[]:

        arr.append([n, 1])

    return arr

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

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

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

num[2]+=1

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

    if i%2==1:

        n=sb(i)

        if len(n)==1 and n[0][1]==1:

            num[i]+=1

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

            num2[i]+=1

for i in range(1,len(num2)):

    cnt[i]=cnt[i-1]+num2[i]

q=int(eval(input()))

for i in range(q):

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

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

import math

q=int(eval(input()))

num=[0]*(10**5+5)

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

num[2]=1

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

    yn=0

    for j in range(2,int(math.sqrt(i))+1):

        if i%j==0:

            yn=1

            break

    if yn==0:

        num[i]=1

        if num[(i+1)//2]==1:

            ans[i]=1

for i in range(1,len(num)):

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

for i in range(q):

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

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

def sb(n):
    arr = []
    temp = n
    for i in range(2, int(-(-(n**0.5) // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


num = [0] * (10**5 + 1)
num2 = [0] * (10**5 + 1)
cnt = [0] * (10**5 + 1)
num[2] += 1
for i in range(2, 10**5 + 1):
    if i % 2 == 1:
        n = sb(i)
        if len(n) == 1 and n[0][1] == 1:
            num[i] += 1
        if num[i] == 1 and num[(i + 1) // 2] == 1:
            num2[i] += 1
for i in range(1, len(num2)):
    cnt[i] = cnt[i - 1] + num2[i]
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((cnt[r] - cnt[l - 1]))

import math

q = int(eval(input()))
num = [0] * (10**5 + 5)
ans = [0] * (10**5 + 5)
num[2] = 1
for i in range(3, 10**5 + 2, 2):
    yn = 0
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            yn = 1
            break
    if yn == 0:
        num[i] = 1
        if num[(i + 1) // 2] == 1:
            ans[i] = 1
for i in range(1, len(num)):
    ans[i] = ans[i - 1] + ans[i]
for i in range(q):
    l, r = list(map(int, input().split()))
    print((ans[r] - ans[l - 1]))

-def sb(n): -    arr = [] -    temp = n -    for i in range(2, int(-(-(n**0.5) // 1)) + 1): -        if temp % i == 0: -            cnt = 0 -            while temp % i == 0: -                cnt += 1 -                temp //= i -            arr.append([i, cnt]) -    if temp != 1: -        arr.append([temp, 1]) -    if arr == []: -        arr.append([n, 1]) -    return arr +import math - -num = [0] * (10**5 + 1) -num2 = [0] * (10**5 + 1) -cnt = [0] * (10**5 + 1) -num[2] += 1 -for i in range(2, 10**5 + 1): -    if i % 2 == 1: -        n = sb(i) -        if len(n) == 1 and n[0][1] == 1: -            num[i] += 1 -        if num[i] == 1 and num[(i + 1) // 2] == 1: -            num2[i] += 1 -for i in range(1, len(num2)): -    cnt[i] = cnt[i - 1] + num2[i] +num = [0] * (10**5 + 5) +ans = [0] * (10**5 + 5) +num[2] = 1 +for i in range(3, 10**5 + 2, 2): +    yn = 0 +    for j in range(2, int(math.sqrt(i)) + 1): +        if i % j == 0: +            yn = 1 +            break +    if yn == 0: +        num[i] = 1 +        if num[(i + 1) // 2] == 1: +            ans[i] = 1 +for i in range(1, len(num)): +    ans[i] = ans[i - 1] + ans[i] -    print((cnt[r] - cnt[l - 1])) +    print((ans[r] - ans[l - 1]))