거듭제곱 탑

729는 여러 가지 방법으로 거듭제곱으로 나타낼 수 있다. $3^6$, $9^3$, $27^2$이 모두 729다. 물론 $729^1$도 729이지만, 이것은 거듭제곱으로 세지 않는다.

여기서는 한 걸음 더 나아간다. 거듭제곱을 ^로 적어서 a^b가 $a^b$를 뜻한다고 하자. 그러면 256은 2^2^3으로도 쓸 수 있고 4^2^2로도 쓸 수 있다. ^는 오른쪽 결합이므로 2^2^3은 $2^{(2^3)}$을 뜻한다.

높이가 $k$인 거듭제곱 탑은 a1^a2^a3^...^ak 꼴의 식이다. 여기서 $k > 1$이고 모든 $a_i$는 1보다 큰 정수다.

정수 $n$을 나타내는 높이 3의 거듭제곱 탑이 주어진다. $n$을 나타내는 높이 3 이상의 거듭제곱 탑은 모두 몇 개인가?

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 하나씩 a^b^c 꼴로 주어지고, $a$, $b$, $c$는 $1 < a, b, c \le 9585$인 정수다. 테스트 케이스의 개수는 주어지지 않으므로 입력의 끝까지 읽어야 한다.

각 테스트 케이스마다 $n = a^{b^c}$이라 할 때, $n$을 높이 3 이상의 거듭제곱 탑으로 나타내는 방법의 수를 한 줄에 하나씩 출력한다.

9585는 답이 항상 $2^{63}$보다 작도록 고른 수다.