|
Наихудший делитель
(Время: 1 сек. Память: 16 Мб Сложность: 23%)
Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго — шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.
Дано число n. Найдите такой его делитель d (само число n и единица считаются делителями числа n), что любой другой делитель числа n лучше, чем d.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n
(1 ≤ n ≤ 105000).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10 | 10 |
| 2 | 239 | 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
