Деление Гольдбаха
Широко известна проблема Гольдбаха! Вот одна из её версий:
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)|.