T. Математическая выгода

Математик Виталий Евгеньевич задумался над вопросом выгоды систем счисления. Он решил, что выгодной системой счисления будет являться та, в которой число имеет наибольшую сумму цифр. Напишите программу, которая по введённому числу определяет основание системы счисления с максимальной выгодой.

Формат ввода

Одно натурально число.

Формат вывода:

Одно натуральное число из диапазона [2;10] — основание системы счисления с максимальной выгодой.
Если таких оснований несколько, выбирается наименьшее.

Примечание

Подробнее о системах счисления можно почитать здесь

Пример

Ввод

12

Вывод

7

Ввод

52

Вывод

9

Решение

Перевод из одной системы счисления в другую поначалу кажется сложной задачей, но только лишь до тех пор, пока не станет понятно, что в ней могут присутствовать цифры не превышающие основание системы счисления.
Так, в троичной системе счисления привычный нам ряд 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 будет выглядеть как 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, а в пятеричной 1, 2, 3, 4, 10, 11, 12, 13, 14, 20.
Обратите внимание, что переход на новый разряд и обновление разрядов, случается ровно в тот момент, когда число становится равно основанию системы счисления. Из этого можно сделать простой вывод: Чтобы перевести число из десятичной системы счисления в троичную, нужно поделить с остатком число на основание. Таким образом мы получим последнюю цифру. Теперь делим число на базу и повторяем операцию, чтобы получить вторую цифру с конца и так, пока число останется больше нуля. Остается только посчитать сумму цифр для систем счисления в диапазоне от десяти до двух.

number = int(input())

best_value = 0
best_base = 0

for base in range(10, 1, -1):
    summa = 0
    num = number
    while num > 0:
        summa += (num % base)
        num //= base
    if summa >= best_value:
        best_value = summa
        best_base = base

print(best_base)