Втеча з вязниці
Зброяр Просперо та гімнаст Тибул підняли народ проти режиму Трьох Товстунів, и повели людей, щоб взяти штурмом їх замок. Однак гвардійцям удалось подавить бунт, зброяра Просперо було заарештовано і поміщено до в’язниці, Тибул же зміг утекти. Тепер гімнаст обдумує як йому врятувати товариша. На камеру, в якій сидить Просперо встановлено кодовий замок. Код визначається трьома числами, кожне з яких може бути в межах від 1 до n. Суок удалось дізнатися, що в правильному коді сума цих трьох чисел є просте число. Звичайно, цієї інформації може виявитися недостатньої для того, щоб точно знати код, але може значно скоротити перебір.
Напишіть програму, яка визначить кількість комбінацій, які потрібно перебрати Тибулу, коли він проникне до тюрми.
Вхідні дані
Ціле число n (1 ≤ n ≤ 10000).
Вихідні дані
Виведіть кількість комбінацій з трьох чисел від 1 до n, сума яких є простим числом.