from sortedcontainers import*
(q,),*e=[[*map(int,s.split())]for s in open(0)]
def spf(n):
 spf=[*range(n+1)]
 for i in range(2,n+1):
  for j in range(i*2,n+1,i):
   spf[j]=i
 return spf
s=spf(10**6)

def Add(i):
  global sl,res
  if s[i]!=i:
    sl.add(s[i])
  else:
    res+=1

def Del(i):
  global sl,res
  if s[i]!=i:
    sl.discard(s[i])
  else:
    res-=1

N=10**6
M=int(N**.5)+1
bucket=[[] for i in range(M)]
ans=[0]*q
for i,(l,r)in enumerate(e):
  if l==1:
    ans[i]=1
  else:
    bucket[(l-1)*M//N]+=(l,r,i),

for i in range(M):
  if i&1:
    bucket[i].sort(key=lambda x:-x[1])
  else:
    bucket[i].sort(key=lambda x:x[1])

sl=SortedList()
res=0
L=R=1

for b in bucket:
  for l,r,i in b:
    while R<r:R+=1;Add(R)
    while L>l:L-=1;Add(L)
    while R>r:Del(R);R-=1
    while L<l:Del(L);L+=1
    # print(l,r,i,sl,sl.bisect_left(l),res)
    ans[i]=sl.bisect_left(l)+res+1
print(*ans,sep='\n')