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.