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

Дано натуральное число 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, b ≤ 10^6) и k (1 ≤ k ≤ 6).

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

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

Примеры