Escape from Prison
The gunsmith Prospero and the gymnast Tibul rallied the people against the regime of the Three Fat Men and led them to storm their castle. However, the guards managed to suppress the revolt, resulting in Prospero's arrest and imprisonment, while Tibul managed to escape. Now, Tibul is contemplating how to rescue his comrade. The cell where Prospero is held has a coded lock. The code is determined by three numbers, each ranging from 1 to n. Suok discovered that the sum of these three numbers in the correct code is a prime number. Although this information may not reveal the exact code, it can significantly reduce the number of combinations Tibul needs to try.
Write a program to determine the number of combinations Tibul needs to try when he infiltrates the prison.
Input
An integer n (1 ≤ n ≤ 10000).
Output
Output the number of combinations of three numbers from 1 to n, where the sum is a prime number.