Extended Happy Numbers

Given a positive integer n, raise each of its digits to the k-th power and sum those values to get S_k(n). For example, S_2(65) = 62 + 52 = 61. Now, consider a sequence n, S_k(n), S_k(S_k(n)) and so on.

The happiness of n with respect to k is the smallest number in this sequence.

Input

Each line is a separate test case that contain three integers a, b (1 ≤ a, b ≤ 10^6) and k (1 ≤ k ≤ 6).

Output

For each tests case calculate the happiness of each integer between a and b, inclusive, with respect to k and print their sum.

Examples