Дано натуральне число \textbf{n}. Піднесемо до \textbf{k} - го степеня кожну його цифру та просумуємо отримані результати. Позначимо результат через \textbf{S_k}(\textbf{n}). Наприклад, \textbf{S_2}(\textbf{65}) = \textbf{6^2} + \textbf{5^2} = \textbf{61}. Побудуємо послідовність \textbf{n}, \textbf{S_k}(\textbf{n}), \textbf{S_k}(\textbf{S_k}(\textbf{n})), … . Щастям числа \textbf{n} по відношенню до \textbf{k} будемо називати найменше число у цій послідовності. \InputFile Кожний рядок є окремим тестом і містить три цілі числа \textbf{a}, \textbf{b} (\textbf{1 }≤ \textbf{a}, \textbf{b} ≤ \textbf{10^6}) та \textbf{k} (\textbf{1 }≤ \textbf{k} ≤ \textbf{6}). \OutputFile Для кожного тесту обчислити щастя для кожного числа від \textbf{a} до \textbf{b} включно по відношенню до \textbf{k} і вивести їх суму.