def setPrime(n, is_prime, primes): is_prime = [0] * (n + 1) for i in range(n + 1): is_prime[i] = True is_prime[0] = False is_prime[1] = False for i in range(n + 1): if (is_prime[i]): j = i * 2 while (j <= n): is_prime[j] = False j += i for i in range(n + 1): if (is_prime[i]): primes.append(i) n = int(input()) is_prime = [] primes = [] cnts = [0] * (3 * n + 1) setPrime(3 * n, is_prime, primes) primes2 = prime2 ans = 0 for c in primes: if (c > n): break for sum in primes2: ans += cnts[sum - c] primes2.remove(c) for a in primes: if (a >= c): break cnts[a + c] += 1 print(ans)