
ZOJ Problem Set  3405
Factoring, i.e., listing all the prime factors, of an integer is a useful skill that often helps to solve math problems. For example, one of the ways to find the GCD (Greatest Common Divisor) or LCM (Least Common Multiple) of two integers is by listing all their prime factors. The GCD is then the product of all the common factors; the LCM is the product of all the remaining ones. The Factor Tree is a tool for finding such prime factorizations. The figure below demonstrates three factor trees of 108. At the beginning a root with a number is given, say N, which is to be factored. Then, the root is factored into two children N_{1} and N_{2} such that N = N_{1} × N_{2} (N_{1} ≥ 2, N_{2} ≥ 2). Note that N_{1} and N_{2} need not be prime. The same factoring process continues until all the leaves are prime. While the prime factorization is unique, the factor tree reflects the order in which the factors were found, and is by no means unique. So, how many factor trees of a number are there? InputThere are no more than 10000 cases. A line containing an integer N (2 ≤ N ≤ 1000000000) is given for each case. OutputPrint the number of factor trees of N in a line for each case. The answer will be fit in a signed 64bit integer. Sample Input12 108 642485760 Sample Output6 140 9637611984000 Author: GAO, Yuan Contest: ZOJ Monthly, September 2010 