시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 46 8 8 19.048%

문제

자연수 N이 주어졌을 때, N의 각 자리수를 K제곱 한 후에 그 합을 구하는 함수를 SK(N)이라고 하자.

예를 들어, S2(65) = 6^2 + 5^2 = 61이다.

따라서, 다음 수열을 생각할 수 있다. N, SK(N), SK(SK(N)), …

이 때, A와 B와 K가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 모든 N으로 각각 수열을 만들었을 때, 그 수열에서 가장 작은 수의 합을 구하는 프로그램을 작성하시오.
 

입력

첫째 줄에 A B K가 주어진다. A와 B는 1,000,000보다 작거나 같은 자연수이고, K는 6보다 작거나 같은 자연수이다. B는 A보다 크거나 같다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

1 5 2

예제 출력

14

힌트

출처