Дано натуральное число \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} и вывести их сумму.