В фирме, в которой работает ваш друг, ввели новый дизайн билетов на маршрутки. Теперь номер билета может быть любым натуральным числом. Радостные пассажиры тут же придумали новый, очень простой способ определения счастливости номера билета. Он состоит в следующем. Пусть номер билета равен \(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\), ... максимальна.