eolymp
bolt
Try our new interface for solving problems
Problems

Exponential Towers

Exponential Towers

Time limit 1 second
Memory limit 128 MiB

The number 729 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 256 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 k to be an expression of the form a[1]^a[2]^a[3]^.. ^a[k], with k > 1, and integers a[i] > 1.

Given a tower of powers of height 3, representing some integer n, how many towers of powers of height at least 3 represent n?

Input data

Contains several test cases, each on a separate line. Each test case has the form a^b^c, where a, b and c are integers, 1 < a, b, c9585.

Output data

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 9585 is carefully chosen such that the output is always less than 2^63.

Examples

Input example #1
4^2^2
8^12^2
8192^8192^8192
2^900^576
Output example #1
2
10
1258112
342025379
Source 2013 ACM North Western European Regional Contest (NWERC), November 24, Problem E