Задачі
False RSA
False RSA
Roman, Serge and Andrew has decided to upgrade the famous RSA encryption algorithm. They think that the limitation that modulo \textbf{n} used in RSA must be a product of two distinct primes is redundant. Instead they plan to use \textbf{n}which is the product of \textbf{k}-th powers of two distinct primes: \textbf{n = p^kq^k}.
However, Nick pointed out that besides all other mathematical problems, the scheme may be easier to crack. That is --- it is difficult to factorize \textbf{n} which is a product of two distinct primes, because it has exactly one non-trivial factorization. On the other hand, in case \textbf{n = p^kq^k} there can be more different non-trivial factorizations. For example, \textbf{100 = 2^2·5^2} has eight non-trivial factorizations: \textbf{100 = 2·50}, \textbf{100 = 2·2·25}, \textbf{100 = 2·2·5·5}, \textbf{100 = 2·5·10}, \textbf{100 = 4·25}, \textbf{100 = 4·5·5}, \textbf{100 = 5·20} and \textbf{100 = 10·10}.
Now Roman, Serge and Andrew wonder --- given \textbf{n = p^kq^k}, how many different non-trivial factorizations of \textbf{n} are there?
\InputFile
The input file contains one integer number \textbf{n} (\textbf{6} ≤ \textbf{n} ≤ \textbf{10^18}, it is guaranteed that \textbf{n = p^kq^k} for different primes \textbf{p} and \textbf{q} and integer \textbf{k} > \textbf{0}).
\OutputFile
Output one integer number --- the number of different non-trivial factorizations of \textbf{n}.
Вхідні дані #1
6
Вихідні дані #1
1