Розширене щасливе число (Topcoder, SRM 334)

Дано натуральне число 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 і вивести їх суму.

Приклади