from collections import defaultdict N = int(input()) array = [1]*(3*N+1) array[0] = 0 array[1] = 0 prime_1 = [] prime_2 = [] i = 2 while i <= 3*N: if array[i]: for j in range(2*i, 3*N+1, i): array[j] = 0 if 3 < i <= N: if i % 3 == 1: prime_1.append(i) elif i % 3 == 2: prime_2.append(i) i += 1 ans = 0 prime_1_1 = defaultdict(int) for i in range(len(prime_1)): for j in range(i+1,len(prime_1)): prime_1_1[prime_1[i]+prime_1[j]] += 1 prime_2_2 = defaultdict(int) for i in range(len(prime_2)): for j in range(i+1,len(prime_2)): prime_2_2[prime_2[i]+prime_2[j]] += 1 for s in prime_1_1: c = array[3+s] for j in prime_2: c += array[j+s] ans += c*prime_1_1[s] for s in prime_2_2: c = array[3+s] for j in prime_1: c += array[j+s] ans += c*prime_2_2[s] print(ans)