Problems
Extended Happy Numbers
Extended Happy Numbers
Given a positive integer \textbf{n}, raise each of its digits to the \textbf{k}-th power and sum those values to get \textbf{S_k}(\textbf{n}). For example, \textbf{S_2}(\textbf{65}) = \textbf{62} + \textbf{52} = \textbf{61}. Now, consider a sequence \textbf{n}, S_k(\textbf{n}), \textbf{S_k}(\textbf{S_k}(\textbf{n})) and so on.
The happiness of \textbf{n} with respect to \textbf{k} is the smallest number in this sequence.
\InputFile
Each line is a separate test case that contain three integers \textbf{a}, \textbf{b} (\textbf{1 }≤ \textbf{a}, \textbf{b} ≤ \textbf{10^6}) and \textbf{k} (\textbf{1 }≤ \textbf{k} ≤ \textbf{6}).
\OutputFile
For each tests case calculate the happiness of each integer between \textbf{a} and \textbf{b}, inclusive, with respect to \textbf{k} and print their sum.
Input example #1
13 13 2 1 5 2 535 538 3
Output example #1
1 14 820