Digit-Power Sequence

Interview

Time limit2sMemory limit128 MB

Summary

For each N from A to B, repeatedly sum the K-th powers of its digits, detect the eventual cycle, and sum the minimum value reached over all sequences.

Level: Medium4 of 10
Topics: Simulation, Math, Hash map
Solved: No attempts yet

Problem

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.

Input

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

Output

Print the answer on one line.

Constraints

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

Examples5

Example 1
Input
```
1 5 2
```
Expected output
```
14
```
Example 2
Input
```
13 13 2
```
Expected output
```
1
```
Example 3
Input
```
10 99 1
```
Expected output
```
450
```
Example 4
Input
```
535 538 3
```
Expected output
```
820
```
Example 5
Input
```
100000 400000 6
```
Expected output
```
5169721292
```