Ложный RSA
Роман, Сергей и Андрей решили усовершенствовать известный алгоритм шифрования RSA. Они считают, что требование, чтобы модуль n, используемый в RSA, был произведением двух различных простых чисел, является излишним. Вместо этого они предлагают использовать n, который является произведением k-тых степеней двух различных простых чисел: n = p^kq^k.
Однако Ник заметил, что, помимо других математических сложностей, такая схема может быть легче взломана. Это связано с тем, что факторизация n, являющегося произведением двух различных простых чисел, сложна, так как у него есть ровно одна нетривиальная факторизация. В случае же n = p^kq^k может существовать больше различных нетривиальных факторизаций. Например, 100 = 2^2·5^2 имеет восемь нетривиальных факторизаций: 100 = 2·50, 100 = 2·2·25, 100 = 2·2·5·5, 100 = 2·5·10, 100 = 4·25, 100 = 4·5·5, 100 = 5·20 и 100 = 10·10.
Теперь Роман, Сергей и Андрей хотят узнать — сколько существует различных нетривиальных факторизаций n, где n = p^kq^k?
Входные данные
Входной файл содержит одно целое число n (6 ≤ n ≤ 10^18, гарантируется, что n = p^kq^k для различных простых чисел p и q и целого числа k > 0).
Выходные данные
Выведите одно целое число — количество различных нетривиальных факторизаций n.