(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)
for i in range(10**6+1):
  if s[i]==i:
    s[i]=0

#https://tjkendev.github.io/procon-library/python/range_query/merge-sort-tree.html
from bisect import bisect
from heapq import merge

# count elements A_i s.t. A_i <= k for i in [l, r)
def query1(N0, data, l, r, k):
    L = l + N0; R = r + N0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += bisect(data[R-1], k-1)
        if L & 1:
            s += bisect(data[L-1], k-1)
            L += 1
        L >>= 1; R >>= 1
    return s

N=len(s)
A=s[:]
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
for i, a in enumerate(A):
    data[N0-1+i] = [a]
for i in range(N, N0):
    data[N0-1+i] = []
for i in range(N0-2, -1, -1):
    *data[i], = merge(data[2*i+1], data[2*i+2])
for l,r in e:
  if l==1:
    ans=1
  else:
    ans=query1(N0,data,l,r+1,l)
  print(ans)