require 'set'

@primes = Set.new([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67])

def is_prime? num
  if num < 2
    return false
  end
  if num <= 67
    return @primes.include?(num)
  else
    @primes.each do |prime|
      return false if num % prime == 0
    end
  end
  miller_rabin_test(num)  
end


def list_of_tests n
  if n < 1373653
    [2,3]
  elsif n < 9080191
    [31,73]
  elsif n < 4759123141
    [2,7,61]
  elsif n < 2152302898747
    [2,3,5,7,11]
  elsif n < 3474749660383
    [2,3,5,7,11,13]
  elsif n < 341550071728321
    [2,3,5,7,11,13,17]
  end
end

def pow_mod(base, power, mod)
  result = 1
  while power > 0
    result = (result * base) % mod if power & 1 == 1
    base = (base * base) % mod
    power >>= 1;
  end
  result
end

def miller_rabin_test num
  n = num-1
  s,d = compute_s_and_d(num)
  list_of_tests(num).each do |a|
    break if a >= num
    x = pow_mod(a,d,num)
    #puts "x = #{x}"
    next if x == 1 or x == n
    skip = false
    (0..s-1).each do |r|
       x = pow_mod(x,2,num)
       #puts "r = #{r}, x = #{x}, n = #{n}"
       return false if x == 1
       if x == n
         skip = true
         break
       end
    end
    next if skip
    return false
  end
  return true
end

def compute_s_and_d n
  s = 0
  d = n - 1
  while d % 2 == 0
    d /= 2
    s += 1
  end
  return [s,d]
end

def find_primes min, max
  if min <= 2
    min = 3
    puts "2"
  end
  start = min.odd? ? min : min+1
  (start..max).step(2) do |num|
    if is_prime?(num)
      STDOUT.write("#{num}\n")
    end
  end
end



ranges = []

STDIN.each_with_index do |line,index|
  next if index == 0
  ranges << line.split.map{|num| num.to_i}
end

ranges.each do |range|
  find_primes *range
  STDOUT.write("\n")
end