Експоненційні вежі
Число 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]^..^a[k], де k > 1, цілі числа a[i] > 1.
За заданою вежею степенів висоти 3, яка представляє деяке ціле число n, визначте кількість веж степенів висоти не більше 3, які представляють n.
Вхідні дані
Складаються з кількох тестів, кожен міститься в окремому рядку. Кожен тест має формат a^b^c, де a, b і c - цілі числа, 1 < a, b, c ≤ 9585.
Вихідні дані
Для кожного тесту виведіть кількість способів, якими може бути представлено число n = a^b^c у вигляді вежі з степенів висоти не більше трьох.
Магічне число 9585 вибрано так, щоб результат завжди був меншим за 2^63.