数论简单知识,不多bibi
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
[[maybe_unused]]const int INF = 1e16 + 50, N = 1e6 + 50;
[[maybe_unused]] typedef std::pair<int, int> pii;
int a[N], primes[N], pos;
bool f[N];
void pre() {
for (int i = 2; i < N; i++) {
if (!f[i]) primes[pos++] = i;
for (int j = 0; primes[j] * i < N; j++) {
f[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
for (int i = 0; i < pos; i++)
if (!f[primes[i] + 2])
a[primes[i] + 2] = 1;
for (int i = 1; i < N; i++)
a[i] += a[i - 1];
}
void solve() {
int n;
std::cin >> n;
std::cout << a[n] << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int Lazy_boy_ = 1;
pre();
std::cin >> Lazy_boy_;
while (Lazy_boy_--)
solve();
return 0;
}