Задача: Нетривиальные разложения
Рома, Саша и Алиса решили модернизировать знаменитый алгоритм шифрования 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\) на множители.
Ваш ответ: