require 'prime'
T = gets.to_i
primes = Prime.each(10 ** 5).to_a
rui = Array.new(10 ** 5 + 1, 0)
cur = 0

1.upto(10 ** 5) do |n|
  if primes[0] == n
    primes.shift
    cur += 1
  end

  rui[n] = cur
end

T.times do
  n = gets.to_i

  puts rui[n]
end