Exponential Towers#7017
The number can be written as a power in several ways: 3^6, 9^3 and 27^2. It can be written as 729^1, of course, but that does not count as a power. We want to go some steps further. To do so, it is convenient to use ^ for exponentiation, so we define a^b = a^b. The number then can be also written as 2^{2^3}, or as 4^{2^2}. Recall that ^ is right associative, so 2^{2^3} means 2^{(2^3)}.
We define a tower of powers of height to be an expression of the form a_1^{a_2^{a_3^{\ldots a_k}}}, with k > 1, and integers a_i > 1.
Given a tower of powers of height , representing some integer , how many towers of powers of height at least represent ?
Contains several test cases, each on a separate line. Each test case has the form a^{b^c}, where , and are integers, 1 < a, b, c \leq 9585.
For each test case, print the number of ways the number n = a^{b^c} can be represented as a tower of powers of height at least three.
The magic number is carefully chosen such that the output is always less than 2^{63}.
Example 1