#include using namespace std; using ll = int64_t; ll N; void input() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N; } inline ll isqrt(ll n) { if (n < 0) return -1; if (n == 0) return 0; ll sq = sqrt(n) - 1; return sq * (sq + 2) < n ? sq + 1 : sq; } vector P; void sieve(ll n) { ll sq = isqrt(n); P.assign(sq+1, true); for (ll i=2; i<=sq; ++i) { if (!P[i]) continue; for (ll j=i*i; j<=sq; j+=i) P[j] = false; } } void solve() { sieve(N); ll l = P.size(); ll ans = 0; for (ll i=2; i