#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()
struct revran {
  const i64 b, e;
  struct iter {
    i64 i;
    constexpr iter(const i64 i) noexcept: i(i) {}
    void operator++() noexcept { --i; }
    constexpr i64 operator*() const noexcept { return i; }
    constexpr bool operator!=(const iter x) const noexcept { return i != x.i; }
  };
  constexpr revran(const i64 e) noexcept: b(0), e(e) {}
  constexpr revran(const i64 b, const i64 e) noexcept: b(b), e(e) {}
  constexpr iter begin() const noexcept { return iter(e - 1); }
  constexpr iter end() const noexcept { return iter(b - 1); }
};

struct ran {
  const i64 b, e;
  struct iter {
    i64 i;
    constexpr iter(const i64 i) noexcept: i(i) {}
    void operator++() noexcept { ++i; }
    constexpr i64 operator*() const noexcept { return i; }
    constexpr bool operator!=(const iter x) const noexcept { return i != x.i; }
  };
  constexpr ran(const i64 e) noexcept: b(0), e(e) {}
  constexpr ran(const i64 b, const i64 e) noexcept: b(b), e(e) {}
  constexpr iter begin() const noexcept { return iter(b); }
  constexpr iter end() const noexcept { return iter(e); }
  constexpr revran rev() const noexcept { return revran(b, e); }
};

constexpr ran rin(const i64 e) noexcept { return ran(1, e + 1); }
constexpr ran rin(const i64 b, const i64 e) noexcept { return ran(b, e + 1); }

i64 cnt(i64 n) {
  i64 c = 0;
  i64 d = 0;
  for(int i = 2;i * i <= n;i++) {
    if(n % i == 0) {
      d++;
      while(n % i == 0) {
        n /= i;
        c++;
      }
    }
  }
  if(n != 1) {
    d++;
    c++;
  }
  if(d <= 1) {
    return c >= 4;
  }
  else {
    return c >= 3;
  }
}

int main() {
  i64 Q;
  cin >> Q;
  vector<i64> sum(101010, 0);
  for(int i = 2;i <= 100000;i++) {
    sum[i] = sum[i - 1] + cnt(i);
  }
  for(int q =0;q < Q;q++) {
    i64 n;
    cin >> n;
    cout << sum[n] << endl;
  }
}

