#include #include using namespace std;

const int MAX = 1e7 + 5; // 最大 n 是 1e7 vector is_prime(MAX, true); vector prefix(MAX, 0); // 前缀和：prefix[i] = 1~i 的素数个数

// 埃氏筛 + 预处理前缀和 void init() { is_prime[0] = is_prime[1] = false; for (long long i = 2; i * i < MAX; ++i) { if (is_prime[i]) { for (long long j = i * i; j < MAX; j += i) is_prime[j] = false; } }

// 计算前缀和
int cnt = 0;
for (int i = 0; i < MAX; ++i) {
    if (is_prime[i]) cnt++;
    prefix[i] = cnt;
}

}

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 加速输入输出（必须加！）

init(); // 只筛一次！

int t;
cin >> t;
while (t--) {
    int n;
    cin >> n;
    cout << prefix[n] << '\n'; // O(1) 输出答案
}
return 0;

}