Простая задачка Печкина
Сегодня, принеся в очередной раз часть косточек, которые он обещал Шарику в задачке "Косточки для Шарика" и которые, как Печкин уже понял, ему придется носить до глубокой старости, почтальон решил в очередной раз проверить математические способности Матроскина:
- Я вот тут что подумал, уважемый мой друг Матроскин, - витьевато начал издалека формулировку своей задачи Печкин. - вот принес я сегодня Шарику 9 косточек. Ты там что-то упоминал, о умнейший из котов, о простых числах. Так вот и вопрос: А сколькими разными способами можно разложить на кучки эти 9 косточек так, чтобы в каждой из кучек было простое число косточек?
- Элементарно, Печкин! Вот смотри: 9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7, итого 4 способа. - быстро ответил Матроскин и гордо удалился на очередное доение своей Бурёнки.
- Да-а, - подумал Печкин, - на практике уже проверено, что при всём желании я не смогу физически поднять и принести более 330 косточек, так что моя задачка действительно простая.
А сможете ли Вы решить задачку Печкина, с которой так быстро справился Матроскин?
Входные данные
Входные данные состоят из нескольких тестовых случаев (не более 20), каждый из которых в отдельной строке содержит очередное число принесённых Печкиным косточек. Известно, что Печкин всегда приносил не менее 2-х косточек.
Выходные данные
Для каждого тестового случая в отдельной строке вывести количество указанных разложений. Учтите, что изменение расположения кучек нового способа не даёт.