e-olymp
Задачи

Деление Гольдбаха

Деление Гольдбаха

Широко известна проблема Гольдбаха! Вот одна из её версий:

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 секунда
Лимит использования памяти 64 MiB
Входные данные
18
19
Выходные данные
2
1