Exponential Towers

Time limit2sMemory limit128 MB

Summary

Given a power tower a^(b^c), count the towers of height at least 3 with bases above 1 that evaluate to the same value.

Level: Hard8 of 10
Topics: Number theory, Combinatorics, Recursion
Solved: No attempts yet

Problem

The number 729 can be written as a power in several ways: $3^6$ , $9^3$ and $27^2$ . It can also be written as $729^1$ , but that does not count as a power.

We go one step further. Write exponentiation with ^, so a^b means $a^b$ . The number 256 can then be written as 2^2^3 or as 4^2^2. The caret is right associative, so 2^2^3 means $2^{(2^3)}$ .

A tower of powers of height $k$ is an expression of the form a1^a2^a3^...^ak with $k > 1$ and integers $a_i > 1$ .

You are given a tower of powers of height 3 that represents an integer $n$ . How many towers of powers of height at least 3 represent $n$ ?

Input

The input has several test cases, one per line. Each test case has the form a^b^c, where $a$ , $b$ and $c$ are integers with $1 < a, b, c \le 9585$ . The number of test cases is not given, so read until the end of the input.

Output

For each test case, let $n = a^{b^c}$ and print on its own line the number of ways $n$ can be represented as a tower of powers of height at least 3.

The number 9585 is chosen so that the answer is always less than $2^{63}$ .

Examples2

Example 1

Input

4^2^2
8^12^2
8192^8192^8192
2^900^576

Expected output

Example 2
Input
```
2^2^2
2^3^3
```
Expected output
```
1
2
```