#include <bits/stdc++.h> using namespace std; const int MXN = 100000000; const int END = 50000000; int T, N, pms[END], pid, psum[MXN + 5]; bitset<MXN + 5> ivl, eff; int read() { int x(0); char c(getchar()); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } void write(int x) { if (x >= 10) write(x / 10); putchar((x % 10) | 48); } int main() { // freopen("pair.in", "r", stdin); // freopen("pair.out", "w", stdout); ivl[0] = ivl[1] = true; for (int i(2); i <= END; ++i) { if (!ivl[i]) { pms[pid++] = i; } if (eff[i]) for (int j(0), x(0); j != pid && (x = i * pms[j]) <= MXN; ++j) { ivl[x] = true; eff[x] = 1; if (!(i % pms[j])) { break; } } else for (int j(0), x(0); j != pid && (x = i * pms[j]) <= MXN; ++j) { ivl[x] = true; if (!(i % pms[j])) { eff[x] = 1; break; } } } for (int i(2); i <= MXN; ++i) { psum[i] = psum[i - 1] + eff[i]; } T = read(); while (T--) { N = read(); write(psum[N]); putchar(10); } // cout << clock() / 1000.0 << endl; return 0; }