Digit-Power Sequence

For a positive integer N, define S_K(N) as the sum of the K-th powers of each decimal digit of N. For example, S_2(65) = 6^2 + 5^2 = 61.

Now form the sequence N, S_K(N), S_K(S_K(N)), .... Given A, B, and K, make this sequence for every integer N with A <= N <= B. For each sequence, take the smallest value that appears in it. Write a program that prints the sum of those smallest values.

The first line contains three integers A, B, and K.

Print the answer on one line.

• 1 <= A <= B <= 1,000,000
• 1 <= K <= 6