Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность.

Сначала он пишет на доске натуральное число \(A\). Каждое следующее число, выписанное им на доске, будет равно степени с основанием \(A\) и показателем, равным предыдущему числу. Другими словами, последовательность будет выглядеть так:

\(x[1] = A\),

\(x[k + 1] = A^{x[k]}\), \(k\) > 0

После этого он решил узнать элемент этой последовательности с минимальным номером, который бы делился на данное число \(N\). Поскольку числа на доске могут быть довольно большими, без вашей помощи ему не обойтись.

Мальчик Влад недавно побывал в Японии и привёз оттуда новую жевательную резинку. Вернувшись в университет после поездки, на первой же паре Влад раздал жвачку всем своим \((N-1)\) однокурсникам и взял одну себе. Дождавшись момента, когда лектор отвернулся к доске, на счёт “три-четыре” все \(N\) студентов дружно начали надувать пузыри. Известно, что \(i\)-й студент надувает пузырь до максимально возможного размера за время \(t_i\), после чего пузырь мгновенно лопается, и студент начинает надувать пузырь заново с той же скоростью.

Всё это время преподаватель настолько увлечён тонкостями квантового математического анализа, что не слышит ничего происходящего в аудитории. И только когда все \(N\) пузырей лопнут одновременно, преподаватель услышит шум и обернётся. И уж тогда студентам достанется, а больше всех тому, кто принёс на пару \(N\) жевательных резинок.

Определите, сколько времени студенты смогут наслаждаться надуванием пузырей, не замечаемые преподавателем.

Например, если \(N=2\), \(t_1=2\), \(t_2=3\), то будет происходить следующее:

Первый студент надувает пузырь с момента времени \(t=0\) до момента времени \(t=2\), потом пузырь лопается, и он надувает пузырь заново — с момента времени \(t=2\) до момента времени \(t=4\), а потом ещё раз — с момента времени \(t=4\) до \(t=6\).

Второй студент надувает пузырь с \(t=0\) до \(t=3\) и ещё раз с \(t=3\) до \(t=6\).

В момент \(t=6\) пузыри лопаются одновременно у обоих студентов, преподаватель оборачивается и говорит: “Всё, Влад! Ты меня достал!”.

Дано натуральное число N. Требуется написать программу, которая находит такое минимальное число M, произведение цифр которого равно N.

В фирме, в которой работает ваш друг, ввели новый дизайн билетов на маршрутки. Теперь номер билета может быть любым натуральным числом. Радостные пассажиры тут же придумали новый, очень простой способ определения счастливости номера билета. Он состоит в следующем. Пусть номер билета равен \(N\). Если \(N<10\), то счастливость числа \(N\) (т.е. и самого билета) равна \(N\), иначе: посчитаем сумму цифр числа \(N\), пусть она равна \(S\) — тогда счастливость числа \(N\) будет равна счастливости числа \(S\).

Например, счастливость билета с номером \(7351\) равна счастливости билета с номером \(16\) (т.к. \(7+3+5+1=16\)), а она в свою очередь равна счастливости билета с номером 7 (т.к. \(1+6=7\)), а последняя просто равна 7 (т.к. \(7<10\)).

Такое определение счастливости вполне устроило обычных пассажиров маршрутки, но совсем не устроило большинство студентов, которые быстро нашли способ без особенных усилий определять счастливость билета. Поэтому, используя это определение, они придумали новую игру: обладатель билета должен разложить его номер в сумму нескольких чисел так, чтобы суммарная счастливость слагаемых была максимальна.

Но и эта игра устроила не всех студентов. Наиболее активные из них заметили, что игра становится ещё более интересной, если раскладывать \(N\) не в сумму, а в произведение чисел, с целью, по-прежнему, максимизировать сумму счастливостей множителей.

Напишите программу, которая будет решать эту задачу, т.е. по данному \(N\) находить такое его представление \(N=a_1\cdot a_2\cdot \ldots\), где все \(a_i\) натуральны, больше единицы, и суммарная счастливость чисел \(a_1\), \(a_2\), ... максимальна.