Рома, Саша и Алиса решили модернизировать знаменитый алгоритм шифрования RSA. Они считают, что ограничение на модуль $$$n$$$, используемый в RSA, должно быть произведением двух различных простых чисел, избыточно. Вместо этого они планируют использовать $$$n$$$, которое представляет собой произведение степеней $$$k$$$ двух различных простых чисел: $$$n = p^kq^k$$$.
Будем называть нетривиальным разложение числа $$$n$$$ на множители, такое, что множителей хотя бы два, и каждый из них строго больше $$$1$$$. Оказалось, что в случае $$$n = p^kq^k$$$ у числа $$$n$$$ может быть несколько различных нетривиальных разложений на множители. Например, $$$100 = 2^2 5^2$$$ имеет восемь нетривиальных разложений: $$$100 = 2\cdot 50$$$, $$$100 = 2\cdot2\cdot25$$$, $$$100 = 2\cdot2\cdot5\cdot5$$$, $$$100=2\cdot5\cdot10$$$, $$$100 = 4\cdot25$$$, $$$100=4\cdot5\cdot5$$$, $$$100=5\cdot20$$$ и $$$100=10\cdot10$$$.
Теперь ребята задаются вопросом: пусть $$$n = p^kq^k$$$, сколько существует различных нетривиальных разложений $$$n$$$ на множители?
На вход подается одно целое число $$$n$$$ ($$$6 \le n \le 10^{18}$$$, гарантируется, что $$$n=p^kq^k$$$ для двух различных $$$p$$$ и $$$q$$$ для целого $$$k > 0$$$).
Выведите одно число — количество нетривиальных разложений $$$n$$$ на множители.
В этой задаче 50 тестов, каждый тест оценивается в 2 балла.
6
1
100
8