Число 729 может быть записано в виде степени несколькими способами: 36, 93 и 272. Конечно, его можно записать как 7291, но это не считается степенью. Мы хотим пойти еще дальше. Для удобства бдем использовать ^ для возведения в степень, поэтому определим a^b = ab. Тогда число 256 можно также записать как 2^2^3 или 4^2^2. Напомним, что ^ является правоассоциативным, поэтому 2^2^3 означает 2^(2^3).

Определим башню степеней высоты k как выражение вида a1^a2^a3^.. ^ak, где k > 1, целые числа ai > 1.

По заданной башне степеней высоты 3, представляющую некоторое целое число n, определите количество башен степеней высоты не более 3, которые представляют n.

Входные данные

Состоит из нескольких тестов, каждый содержится в отдельной строке. Каждый тест имеет формат a^b^c, где a, b и c - целые числа, 1 < a, b, c ≤ 9585.

Выходные данные

Для каждого теста выведите количество способов, которыми может быть представлено число n = a^b^c в виде башни из степеней высоты не более трех.

Магическое число 9585 выбрано так, чтобы результат всегда был меньше 263.