Оружейник Просперо и гимнаст Тибул подняли народ против режима Трех Толстяков, и повели людей, чтобы взять штурмом их дворец. Однако гвардейцам удалось подавить бунт, оружейник Просперо был арестован и заключен в тюрьму, Тибул же успел спастись бегством. Теперь гимнаст обдумывает как ему спасти товарища. На камеру, в которой сидит Просперо установлен кодовый замок. Код определяется тремя числами, каждое из которых может быть в пределах от 1 до n. Суок удалось узнать, что в правильном коде сумма этих трех чисел является простым числом. Естественно, этой информации может оказаться недостаточно для того, чтобы точно знать код, но может значительно сократить перебор.

Напишите программу, определяющую количество комбинаций, которые нужно перебрать Тибулу, когда он проникнет в тюрьму.

Входные данные

Целое число n (1 ≤ n ≤ 10000).

Выходные данные

Выведите количество комбинаций из трех чисел от 1 до n таких, что сумма чисел является простым числом.