False RSA
Roman, Serge and Andrew has decided to upgrade the famous RSA encryption algorithm. They think that the limitation that modulo n used in RSA must be a product of two distinct primes is redundant. Instead they plan to use nwhich is the product of k-th powers of two distinct primes: 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 n which is a product of two distinct primes, because it has exactly one non-trivial factorization. On the other hand, in case n = p^kq^k there can be more different non-trivial factorizations. For example, 100 = 2^2·5^2 has eight non-trivial factorizations: 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 and 100 = 10·10.
Now Roman, Serge and Andrew wonder — given n = p^kq^k, how many different non-trivial factorizations of n are there?
Input
The input file contains one integer number n (6 ≤ n ≤ 10^18, it is guaranteed that n = p^kq^k for different primes p and qand integer k > 0).
Output
Output one integer number — the number of different non-trivial factorizations of n.