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

Ділення Гольдбаха

Ділення Гольдбаха

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Широко відома проблема Гольдбаха! Ось одна з її версій:

1) Довільне непарне число більше 17 можна записати у вигляді суми трьох непарних простих чисел;

2) Довільне парне число більше 6 можна записати у вигляді суми двох непарних простих чисел.

Один з любителів математичних проблем вирішив більш детально вивчити гіпотезу Гольдбаха. Він увів новий термін: ділення Гольдбаха. Якщо число парне, то ми розкладаємо його на суми двох різних простих непарних, а якщо непарне - то на суми трьох різних простих непарних. Такий спосіб разкладу для заданого N назвемо діленням Гольдбаха і позначимо як G(N).

Наприклад, якщо N = 18, то існує два різних разклади на вказані суми для заданого N.

18 = 5 + 13 = 7 + 11

Якщо N = 19, то існує всього один спосіб розкласти задане число N.

19 = 3 + 5 + 11

Ваше завдання: знаючи задане число N, знайти |G(N)|, тобто кількість різних G(N).

Вхідні дані

Вхідні дані містять декілька тестових випадків.

Кожен тест у окремому рядку містить одне єдине число N (1N20000).

Введення продовжується до кінця вхідного файлу.

Вихідні дані

Для кожного тестового випадку вивести у окремому рядку одне число - знайдене значення |G(N)|.

Приклад

Вхідні дані #1
18
19
Вихідні дані #1
2
1