#include using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define get_unique(x) x.erase(unique(all(x)), x.end()); typedef long long ll; typedef complex Complex; const int INF = 1e9; const ll LINF = 1e18; const ll MOD = LINF; template bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } template vector make_vec(size_t a) { return vector(a); } template auto make_vec(size_t a, Ts... ts) { return vector(ts...))>(a, make_vec(ts...)); } struct NumberTheoreticTransform { ll ext_gxd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1; y = 0; return a; } ll q = a / b; ll g = ext_gxd(b, a - q * b, x, y); ll z = x - q * y; x = y; y = z; return g; } ll modinv(ll a, ll m) { ll x, y; ext_gxd(a, m, x, y); x %= m; if (x < 0) x += m; return x; } ll modpow(ll a, ll n, ll m) { ll ret = 1; ll now = a; while (n > 0) { if (n % 2 == 1) ret = ret * now % m; now = now * now % m; n /= 2; } return ret; } void ntt(vector& a, ll mod, bool inv = 0) { const int n = sz(a); assert((n & (n - 1)) == 0); const ll g = 3; ll h = modpow(g, (mod - 1) / n, mod); if (inv) h = modinv(h, mod); int i = 0; for (int j = 1; j < n - 1; j++) { for (int k = n >> 1; k > (i ^= k); k >>= 1) { }; if (j < i) swap(a[i], a[j]); } for (int m = 1; m < n; m *= 2) { const int m2 = m * 2; const ll base = modpow(h, n / m2, mod); ll w = 1; for (int x = 0; x < m; x++) { for (int s = x; s < n; s += m2) { ll u = a[s]; ll d = a[s + m] * w % mod; a[s] = u + d; if (a[s] >= mod) a[s] -= mod; a[s + m] = u - d; if (a[s + m] < 0) a[s + m] += mod; } w = w * base % mod; } } for (auto& x : a) { if (x < 0) x += mod; } if (inv) { const int n_inv = modinv(n, mod); for (auto& x : a) x = x * n_inv % mod; } } vector convolution(const vector& a, vector& b, ll mod) { int ntt_size = 1; while (ntt_size < sz(a) + sz(b)) ntt_size <<= 1; vector _a = a, _b = b; _a.resize(ntt_size); _b.resize(ntt_size); ntt(_a, mod); ntt(_b, mod); for (int i = 0; i < ntt_size; i++) { _a[i] *= _b[i]; _a[i] %= mod; } ntt(_a, mod, 1); return _a; } vector modconv(vector a, vector b, ll mod = MOD) { for (auto& x : a) x %= mod; for (auto& x : b) x %= mod; auto x = convolution(a, b, 167772161); auto y = convolution(a, b, 469762049); auto z = convolution(a, b, 1224736769); const ll mod1 = 167772161, mod2 = 469762049, mod3 = 1224736769; const ll mod1_inv_mod2 = modinv(mod1, mod2); const ll mod1mod2_inv_mod3 = modinv(mod1 * mod2, mod3); const ll mod1mod2_mod = mod1 * mod2 % mod; vector ret(sz(x)); for (int i = 0; i < sz(x); i++) { ll v1 = (y[i] - x[i]) * mod1_inv_mod2 % mod2; if (v1 < 0) v1 += mod2; ll v2 = (z[i] - (x[i] + mod1 * v1) % mod3) * mod1mod2_inv_mod3 % mod3; if (v2 < 0) v2 += mod3; ll constants3 = (x[i] + mod1 * v1 + mod1mod2_mod * v2) % mod; if (constants3 < 0) constants3 += mod; ret[i] = constants3; } return ret; } }; int main() { vector prime; for (int p = 2; p <= 300000; p++) { bool isprime = 1; for (int d = 2; d * d <= p; d++) { isprime &= (p % d > 0); } if (isprime) { prime.push_back(p); } } NumberTheoreticTransform ntt; int n; cin >> n; vector v(n + 1); for (int i = 0; prime[i] <= n && i < sz(prime); i++) { v[prime[i]]++; } auto c = ntt.modconv(ntt.modconv(v, v), v); ll ans = 0; for (int i = 0; prime[i] <= 3 * n && i < sz(prime); i++) { ans += c[prime[i]]++; } vector w(2 * n + 1); for (int i = 0; prime[i] <= n && i < sz(prime); i++) { w[2 * prime[i]]++; } auto d = ntt.modconv(v, w); for (int i = 0; prime[i] <= 3 * n && i < sz(prime); i++) { ans -= 3 * d[prime[i]]; } cout << ans / 6 << endl; }