Ділення Гольдбаха
Широко відома проблема Гольдбаха! Ось одна з її версій:
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 (1 ≤ N ≤ 20000).
Введення продовжується до кінця вхідного файлу.
Вихідні дані
Для кожного тестового випадку вивести у окремому рядку одне число - знайдене значення |G(N)|.