620. Открытка с уравнением

Не решаласьСредняя

Кодерун нашёл под ёлкой первый подарок и распаковал его. Внутри был учебник по теории чисел и новогодняя открытка с предложением решить это уравнение:

x + p ( x ) = n x + p(x) = n , где n n — заданное натуральное число, а p ( x ) p(x) обозначает количество различных простых делителей числа x x . Например, p ( 1 ) = 0 , p ( 4 ) = 1 , p ( 12 ) = 2 , p ( 30 ) = 3 p(1) = 0, p(4) = 1, p(12) = 2, p(30) = 3 . Помогите ему найти количество целочисленных положительных решений этого уравнения, то есть количество целых x > 0 x > 0 , для которых верно равенство. Простым называется число, у которого ровно 2 2 различных делителя. Простые делители числа x x — делители x x , которые являются простыми числам

Формат ввода

Вам дано число 1 ≤ n ≤ 1 0 12 1 \le n \le 10^{12} .

Формат вывода

Выведите количество положительных целых решений уравнения.

Ограничения

Ограничение времени
4 с
Ограничение памяти
256 МБ

Примеры

Пример 1

Ввод
12
Вывод
2

Пример 2

Ввод
2
Вывод
0

Пример 3

Ввод
3
Вывод
1

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти