|
Будем говорить, что число a лучше числа b, если сумма цифр
a больше суммы цифр b, а в случае равенства сумм их цифр, если
число a меньше числа b. Например, число 124 лучше числа 123,
так как у первого из них сумма цифр равна семи, а у второго - шести. Также,
число 3 лучше 111, так как у них равны суммы цифр, но первое из них меньше.
Требуется найти такой делитель заданного числа, который лучше любого
другого делителя. Само число и единица считаются делителями числа.
Формат входных данных:
Вводится заданное число N
(1 ≤ N ≤ 100 000).
Формат выходных данных:
Выведите наилучший делитель числа N.
Пример входных и выходных данных:
| 
