import numpy as np
from numpy.fft import fft, ifft
from sys import stdin

def solve():
  for line in stdin:
    n = int(line)
    n3 = n * 3
    isp = np.ones(n3 + 1, np.uint8)
    v = int(n3 ** 0.5)
    for i in range(2, v + 1):
      if isp[i]:
        isp[i*i::i] = 0
    isp[0] = isp[1] = 0
    s = 1 << (((n3 + 1) * 2 - 1).bit_length() - 1)
    f = np.zeros(s, np.complex128)
    f[:n+1] = isp[:n+1]
    p1, fg = fft(f), np.zeros(s, np.complex128)
    p2 = np.concatenate((p1[::2], p1[::2]))
    p3 = np.concatenate((p1[::3], p1[3-s%3::3], p1[s%3::3]))
    e2 = (p1 * p1 - p2) / 2.0
    fg = (e2 * p1 - p1 * p2 + p3) / 3.0
    g = ifft(fg).real.round().astype(np.int64)
    print(np.sum(g[np.nonzero(isp)]))

solve()