На досуге вы любите почитать сборники занимательных задач по математике. Недавно вы наткнулись в одном из таких сборников на следующую задачу:

Есть бесконечный резервуар с водой и два пустых сосуда объёмом 5 и 12 литров. Можно наливать воду из резервуара в любой сосуд до его заполнения, переливать воду из —одного сосуда в другой до заполнения второго или опустошения первого (смотря что будет раньше) и выливать воду из сосуда на землю до полного опустошения сосуда. Как таким образом можно отмерить 3 литра?

Вы решили написать программу, которая будет решать подобные задачи для произвольных объёмов сосудов.

В городе N строят метро. Вася, житель города N, хочет знать, сколько станций окажутся недалеко от его дома. Помогите ему.

Город N отличается очень строгой планировкой улиц: каждая улица идёт либо строго с юга на север, либо строго с востока на запад; при этом расстояние между соседними параллельными улицами одинаково. Соответственно, в городе есть много перекрёстков, расположенных в вершинах квадратной сетки. По планам, первая линия метро будет прямой и будет иметь станции на каждом перекрёстке, через который она пройдёт. Вася считает, что станция находится недалеко от его дома, если расстояние по прямой от его дома до станции не превосходит некоторой фиксированной величины \(R\).

Рассмотрим два числа \(a\) и \(b\). По ним можно однозначно определить такое целое \(k\), что \(\) b^k\leq a< b^{k+1}; \(\) это \(k\) мы будем называть целой частью логарифма \(a\) по основанию \(b\).

Напишите программу, которая будет вычислять целую часть логарифма.

Мальчик Влад недавно побывал в Японии и привёз оттуда новую жевательную резинку. Вернувшись в университет после поездки, на первой же паре Влад раздал жвачку всем своим \((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\). Если \(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\), ... максимальна.