"""

10**5以下の各数に対して、その数字以下の2017に似た数の個数をカウントしておく。

"""

prime = [1]*(10**5+1)

prime[0] = 0

prime[1] = 1

count = [0,0]

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

    count.append(count[-1])

    if prime[i]:

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

            prime[j] = 0

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

            count[-1] += 1



Q = int(eval(input()))

for _ in range(Q):

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

    print((count[r]-count[l-1]))
prime = [1]*(100001)

prime[0] = 0

prime[1] = 0

for i in range(2,100001):

    if prime[i]:

        for j in range(i*i,100001,i):

            prime[j] = 0



for i in range(100000,-1,-1):

    if prime[i]:

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

            prime[i] = 0



from itertools import accumulate

accum = list(accumulate(prime))



Q = int(eval(input()))

for _ in range(Q):

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

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

"""
10**5以下の各数に対して、その数字以下の2017に似た数の個数をカウントしておく。
"""
prime = [1] * (10**5 + 1)
prime[0] = 0
prime[1] = 1
count = [0, 0]
for i in range(2, 10**5 + 1):
    count.append(count[-1])
    if prime[i]:
        for j in range(i * i, 10**5 + 1, i):
            prime[j] = 0
        if i > 2 and prime[(i + 1) // 2] == 1:
            count[-1] += 1
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((count[r] - count[l - 1]))

prime = [1] * (100001)
prime[0] = 0
prime[1] = 0
for i in range(2, 100001):
    if prime[i]:
        for j in range(i * i, 100001, i):
            prime[j] = 0
for i in range(100000, -1, -1):
    if prime[i]:
        if prime[(i + 1) // 2] != 1:
            prime[i] = 0
from itertools import accumulate

accum = list(accumulate(prime))
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((accum[r] - accum[l - 1]))

-""" -10**5以下の各数に対して、その数字以下の2017に似た数の個数をカウントしておく。 -""" -prime = [1] * (10**5 + 1) +prime = [1] * (100001) -prime[1] = 1 -count = [0, 0] -for i in range(2, 10**5 + 1): -    count.append(count[-1]) +prime[1] = 0 +for i in range(2, 100001): -        for j in range(i * i, 10**5 + 1, i): +        for j in range(i * i, 100001, i): -        if i > 2 and prime[(i + 1) // 2] == 1: -            count[-1] += 1 +for i in range(100000, -1, -1): +    if prime[i]: +        if prime[(i + 1) // 2] != 1: +            prime[i] = 0 +from itertools import accumulate + +accum = list(accumulate(prime)) -    print((count[r] - count[l - 1])) +    print((accum[r] - accum[l - 1]))