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

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

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

x+p(x)=nx + p(x) = n

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

Формат ввода

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

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

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

Ограничения

Ограничение времени

4 с

Ограничение памяти

256 МБ

Пример 1

Ввод
12
Вывод
2

Пример 2

Ввод
2
Вывод
0

Пример 3

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