#include <bits/stdc++.h>
using namespace std;

signed main() {
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  vector<int> np(3 * N + 1);
  vector<int> 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<long long> 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;
}