eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Простая задачка Печкина

Простая задачка Печкина

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Сегодня, принеся в очередной раз часть косточек, которые он обещал Шарику в задачке "Косточки для Шарика" и которые, как Печкин уже понял, ему придется носить до глубокой старости, почтальон решил в очередной раз проверить математические способности Матроскина:

- Я вот тут что подумал, уважемый мой друг Матроскин, - витьевато начал издалека формулировку своей задачи Печкин. - вот принес я сегодня Шарику 9 косточек. Ты там что-то упоминал, о умнейший из котов, о простых числах. Так вот и вопрос: А сколькими разными способами можно разложить на кучки эти 9 косточек так, чтобы в каждой из кучек было простое число косточек?

- Элементарно, Печкин! Вот смотри: 9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7, итого 4 способа. - быстро ответил Матроскин и гордо удалился на очередное доение своей Бурёнки.

- Да-а, - подумал Печкин, - на практике уже проверено, что при всём желании я не смогу физически поднять и принести более 330 косточек, так что моя задачка действительно простая.

А сможете ли Вы решить задачку Печкина, с которой так быстро справился Матроскин?

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

Входные данные состоят из нескольких тестовых случаев (не более 20), каждый из которых в отдельной строке содержит очередное число принесённых Печкиным косточек. Известно, что Печкин всегда приносил не менее 2-х косточек.

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

Для каждого тестового случая в отдельной строке вывести количество указанных разложений. Учтите, что изменение расположения кучек нового способа не даёт.

Пример

Входные данные #1
2
9
200
Выходные данные #1
1
4
9845164