f=[True]*(10**5+1)

like=[False]*(10**5+1)

f[0]=False

f[1]=False

import math

for i in range(2,len(f)):

  fact=True

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

    if i%j==0:

      fact=False

      break

  

  if fact:

    f[i]=True

    if i*2-1<len(like):

      like[i*2-1]=True

    for p in range(i*2,len(f),i):

      f[p]=False



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

cur=0

for i in range(len(sums)):

  if f[i] and like[i]:

    sums[i]=cur+1

    cur+=1

  else:

    sums[i]=cur



Q=int(eval(input()))

for i in range(Q):

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

  if l>0:

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

  else:

    print((sums[r]))

f=[True]*(10**5+1)

like=[False]*(10**5+1)

f[0]=False

f[1]=False

import math

for i in range(2,len(f)):

  if not f[i]:

    continue

  fact=True

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

    if i%j==0:

      fact=False

      break

  

  if fact:

    f[i]=True

    if i*2-1<len(like):

      like[i*2-1]=True

    for p in range(i*2,len(f),i):

      f[p]=False



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

cur=0

for i in range(len(sums)):

  if f[i] and like[i]:

    sums[i]=cur+1

    cur+=1

  else:

    sums[i]=cur



Q=int(eval(input()))

for i in range(Q):

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

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

f = [True] * (10**5 + 1)
like = [False] * (10**5 + 1)
f[0] = False
f[1] = False
import math

for i in range(2, len(f)):
    fact = True
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            fact = False
            break
    if fact:
        f[i] = True
        if i * 2 - 1 < len(like):
            like[i * 2 - 1] = True
        for p in range(i * 2, len(f), i):
            f[p] = False
sums = [0] * (10**5 + 1)
cur = 0
for i in range(len(sums)):
    if f[i] and like[i]:
        sums[i] = cur + 1
        cur += 1
    else:
        sums[i] = cur
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    if l > 0:
        print((sums[r] - sums[l - 1]))
    else:
        print((sums[r]))

f = [True] * (10**5 + 1)
like = [False] * (10**5 + 1)
f[0] = False
f[1] = False
import math

for i in range(2, len(f)):
    if not f[i]:
        continue
    fact = True
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            fact = False
            break
    if fact:
        f[i] = True
        if i * 2 - 1 < len(like):
            like[i * 2 - 1] = True
        for p in range(i * 2, len(f), i):
            f[p] = False
sums = [0] * (10**5 + 1)
cur = 0
for i in range(len(sums)):
    if f[i] and like[i]:
        sums[i] = cur + 1
        cur += 1
    else:
        sums[i] = cur
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((sums[r] - sums[l - 1]))

+    if not f[i]: +        continue -    if l > 0: -        print((sums[r] - sums[l - 1])) -    else: -        print((sums[r])) +    print((sums[r] - sums[l - 1]))