import scala.io.StdIn._
object Main extends App {

  val prime = primes(100000)
  val isM = Array.fill(100001){1}.also{a ⇒ a(0) = 0; a(1) = 0}
  for (i ← prime.indices) {
    for (j ← 0 until upperLimit(0, i + 1, prime, 100000 / prime(i))) {
      isM(prime(i) * prime(j)) = 0
    }
    isM(prime(i)) = 0
    if (prime(i).toLong * prime(i) * prime(i) <= 100000) isM(prime(i) * prime(i) * prime(i)) = 0
  }
  for (i ← isM.indices.tail) isM(i) += isM(i - 1)
  for (_ ← 0 until readInt()) {
    val n = readInt()
    println(isM(n))
  }

  def upperLimit(from: Int, until: Int, array: Array[Int], target: Int): Int = {
    var left = from
    var right = until
    while(left < right){
      val mid = (left + right) / 2
      if (array(mid) <= target) left = mid + 1
      else right = mid
    }
    right
  }
  def primes(upperLimit: Int): Array[Int] = {
    val isPrime = Array.fill(upperLimit + 1){true}
    for (i ← 2 to math.sqrt(upperLimit).ceil.toInt if isPrime(i)) {
      for (j ← i * i to upperLimit by i){
        isPrime(j) = false
      }
    }
    (2 to upperLimit).filter(isPrime).toArray
  }
  implicit class Scope[T](val value: T) extends AnyVal {
    def let[A](@inline func: T ⇒ A): A = func(value)
    def also(@inline func: T ⇒ Unit): T = {func(value);value}
  }
}
