def factorization(n):

 p=2

 fcr=[]

 while p*p<=n:

  while n%p==0:

   fcr.append(p)

   n//=p

  p+=1

 if n>1:

  fcr.append(n)

 return fcr



q=int(eval(input()))



cnt=1

p_list=[1]

q_list=[0]

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

 a=factorization(i)

 b=factorization((i+1)//2)



 if len(a)==len(b)==1:

  cnt+=1

  q_list.append(1)

 else:

  q_list.append(0)



 p_list.append(cnt)



for i in range(q):

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



 c=p_list[r//2]-p_list[l//2]

 if q_list[l//2]==1:

  print((c+1))

 else:

  print(c)
def eratosthenes(n):

 is_p=[1]*n

 p_list=[]



 is_p[0]=0

 is_p[1]=0



 for i in range(2,n):

  if is_p[i]:

   p_list.append(i)

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

    is_p[j] = 0



# return p_list

 return is_p



q=int(eval(input()))



lim=10**5+1

is_p=eratosthenes(lim)



#print(is_p)



b=[0]

for i in range(1,lim+1):

 if is_p[i-1]==1 and is_p[i//2]==1:

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

 else:

  b.append(b[i-1])



#print(b)



for i in range(q):

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

 print((b[r+1]-b[l]))
def factorization(n):
    p = 2
    fcr = []
    while p * p <= n:
        while n % p == 0:
            fcr.append(p)
            n //= p
        p += 1
    if n > 1:
        fcr.append(n)
    return fcr


q = int(eval(input()))
cnt = 1
p_list = [1]
q_list = [0]
for i in range(3, 10**5 + 1, 2):
    a = factorization(i)
    b = factorization((i + 1) // 2)
    if len(a) == len(b) == 1:
        cnt += 1
        q_list.append(1)
    else:
        q_list.append(0)
    p_list.append(cnt)
for i in range(q):
    l, r = list(map(int, input().split()))
    c = p_list[r // 2] - p_list[l // 2]
    if q_list[l // 2] == 1:
        print((c + 1))
    else:
        print(c)

def eratosthenes(n):
    is_p = [1] * n
    p_list = []
    is_p[0] = 0
    is_p[1] = 0
    for i in range(2, n):
        if is_p[i]:
            p_list.append(i)
            for j in range(i * i, n, i):
                is_p[j] = 0
    # return p_list
    return is_p


q = int(eval(input()))
lim = 10**5 + 1
is_p = eratosthenes(lim)
# print(is_p)
b = [0]
for i in range(1, lim + 1):
    if is_p[i - 1] == 1 and is_p[i // 2] == 1:
        b.append(b[i - 1] + 1)
    else:
        b.append(b[i - 1])
# print(b)
for i in range(q):
    l, r = list(map(int, input().split()))
    print((b[r + 1] - b[l]))

-def factorization(n): -    p = 2 -    fcr = [] -    while p * p <= n: -        while n % p == 0: -            fcr.append(p) -            n //= p -        p += 1 -    if n > 1: -        fcr.append(n) -    return fcr +def eratosthenes(n): +    is_p = [1] * n +    p_list = [] +    is_p[0] = 0 +    is_p[1] = 0 +    for i in range(2, n): +        if is_p[i]: +            p_list.append(i) +            for j in range(i * i, n, i): +                is_p[j] = 0 +    # return p_list +    return is_p -cnt = 1 -p_list = [1] -q_list = [0] -for i in range(3, 10**5 + 1, 2): -    a = factorization(i) -    b = factorization((i + 1) // 2) -    if len(a) == len(b) == 1: -        cnt += 1 -        q_list.append(1) +lim = 10**5 + 1 +is_p = eratosthenes(lim) +# print(is_p) +b = [0] +for i in range(1, lim + 1): +    if is_p[i - 1] == 1 and is_p[i // 2] == 1: +        b.append(b[i - 1] + 1) -        q_list.append(0) -    p_list.append(cnt) +        b.append(b[i - 1]) +# print(b) -    c = p_list[r // 2] - p_list[l // 2] -    if q_list[l // 2] == 1: -        print((c + 1)) -    else: -        print(c) +    print((b[r + 1] - b[l]))