#!python3
import sys

DEBUG = False
MAX = 10000000

def abend(mess):
  print(mess)
  exit(1)

# even: 1 odd: -1

last = (MAX//2) + 1
ptable = [0] * (MAX+1)
for i in range(2,last+1):
  if ptable[i] == 0:  # for primes
    for j in range(i,len(ptable),i):
      if ptable[j] == 0: ptable[j] = -1
      else: ptable[j] *= -1
for i in range(last,len(ptable),1):
  if ptable[i] == 0: ptable[i] = -1  # get the upper primes too
if DEBUG: print(ptable)

tot = 0
for i in range(2,len(ptable)):
  tot += ptable[i]
  ptable[i] = tot
if DEBUG: print(ptable)
 
n = int(input())
for trial in range(n):
  case = input().split()
  if len(case) != 2: abend("bad case spec")
  lower = int(case[0])
  upper = int(case[1])
  if (lower < 1) or (lower > MAX): abend("lower out of range")
  if (upper < 1) or (upper > MAX): abend("upper out of range")
  if upper < lower: abend("upper less than lower")

  ans = ptable[upper] - ptable[lower-1]
  print(ans)