#include using namespace std; signed main() { ios::sync_with_stdio(false); int N; cin >> N; vector np(3 * N + 1); vector primes; for (int i = 2; i <= 3 * N; ++i) { if (np[i]) continue; primes.emplace_back(i); for (int j = i + i; j <= 3 * N; j += i) np[j] = 1; } long long ans = 0; vector dp(3 * N + 1); for (int i = 1; i < primes.size() && primes[i] <= N; ++i) { for (int j = primes.size() - 1; primes[j] > primes[i]; --j) ans += dp[primes[j] - primes[i]]; for (int j = 0; j < i; ++j) ++dp[primes[i] + primes[j]]; } cout << ans << endl; return 0; }