Сложное число может быть разложено на множители разными путями. К примеру, если исключить умножение на единицу, 24 может быть разложено семью разными способами:

Напомню, что цифровой корень числа по основанию 10 можно найти, складывая цифры этого числа, и повторяя этот процесс, пока в результате не получится число меньше 10. Таким образом, цифровой корень числа 467 равен 8.

Назовем Суммой Цифровых Корней (СЦК) сумму цифровых корней каждого из множителей числа.
Таблица ниже демонстрирует все значения СЦК для числа 24.

Максимальная Сумма Цифровых Корней для 24 равна 11.
Функция mdrs(n) возвращает максимальную Сумму Цифровых Корней для числа n. Итак, mdrs(24)=11.
Найдите mdrs(n) для 1 n 1,000,000.