数字 $729$ 可以以多种方式写成幂的形式：$3^6$、$9^3$ 和 $27^2$。当然，它也可以写成 $729^1$，但这不算作幂。我们希望更进一步。为此，我们使用 ^ 表示幂运算，即定义 $a^b = a^b$。那么数字 $256$ 也可以写成 $2^{2^3}$ 或 $4^{2^2}$。回想一下，^ 是右结合的，所以 $2^{2^3}$ 表示 $2^{(2^3)}$。

我们定义高度为 $k$ 的幂塔为形式为 $a_1^{a_2^{a_3^{\dots^{a_k}}}}$ 的表达式，其中 $k > 1$，且整数 $a_i > 1$。

给定一个表示某个整数 $n$ 的高度为 $3$ 的幂塔，有多少种高度至少为 $3$ 的幂塔表示 $n$？

输入格式

输入文件包含多个测试用例，每个测试用例占一行。每个测试用例的形式为 $a^b^c$，其中 $a, b, c$ 为整数，$1 < a, b, c \le 9585$。

输出格式

对于每个测试用例，输出将数字 $n = a^{b^c}$ 表示为高度至少为 $3$ 的幂塔的方法数。

神奇数字 $9585$ 是经过精心挑选的，使得输出结果始终小于 $2^{63}$。

样例

输入格式 1

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

输出格式 1

2
10
1258112
342025379