eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Расширенное счастливое число

Расширенное счастливое число

Лимит времени 3 секунды
Лимит использования памяти 64 MiB

Дано натуральное число n. Возведем в k - ую степень каждую его цифру и просуммируем полученные результаты. Обозначим результат через S_k(n). Например, S_2(65) = 6^2 + 5^2 = 61. Построим последовательность n, S_k(n), S_k(S_k(n)), … .

Счастьем числа n по отношению к k будем называть наименьшее число в этой последовательности.

Входные данные

Каждая строка является отдельным тестом и содержит три целых числа a, b (1 a, b10^6) и k (1 k6).

Выходные данные

Для каждого теста вычислить счастье каждого числа от a до b включительно по отношению к k и вывести их сумму.

Пример

Входные данные #1
13 13 2
1 5 2
535 538 3
Выходные данные #1
1
14
820