나이 속이기

시간 제한8초메모리 제한512 MB

요약

현재 나이와 현재 주장한 나이가 주어질 때, 어떤 진법으로 읽으면 실제 나이와 같아지는 수를 매년 줄이지 않으면서 C살에 주장할 수 있는 가장 작은 값을 구한다.

난이도: 보통10점 중 6점
유형: 정수론, 동적 계획법, 완전 탐색
정답자: 아직 제출이 없습니다

문제

새 동네로 이사했다. 새 삶을 시작하면서 한 가지를 결심했다. 나이를 속이는 것이다. 이 동네에는 내 과거를 아는 사람이 없으니 곧바로 들킬 걱정은 없다. 그래도 양심이 조금 걸려서, $M$ 진법 수로 읽었을 때 실제 나이와 같아지는 값만 말하기로 했다. 여기서 $2 \le M \le 16$ 이다. 사람들은 내가 말한 나이를 10진수로 읽으므로 내 나이를 실제와 다르게 안다.

앞으로도 실제 나이가 드러나면 안 된다. 그래서 규칙 세 가지를 지킨다. 한 해에 나이를 한 번만 말한다. 말하는 나이에는 10진 숫자 '0'부터 '9'까지만 쓴다. 10진수로 읽은 값이 작년에 말한 나이보다 작아지지 않는다.

해마다 쓰는 진법은 서로 달라도 된다.

몇 해가 지난 뒤에는 나이를 얼마라고 말할 수 있는가?

입력

입력은 데이터 집합 여러 개로 이루어진다. 각 데이터 집합은 한 줄에 정수 $A$ , $B$ , $C$ 가 공백으로 구분되어 주어진다. $A$ 는 지금의 실제 나이(10진수), $B$ 는 지금 말하고 있는 나이(10진수가 아닐 수 있다), $C$ 는 말할 나이를 구하려는 시점의 실제 나이(10진수)다. $0 \le A < C \le 200$ 이고, $B$ 는 여덟 자리까지다. 세 수에는 '0'부터 '9' 외의 숫자가 나오지 않는다.

$A = B = C = -1$ 인 줄이 입력의 끝을 나타낸다. 이 줄은 처리하지 않는다.

출력

각 데이터 집합마다 실제 나이가 $C$ 가 되었을 때 말할 수 있는 가장 작은 나이를 한 줄에 출력한다. 지금 말하고 있는 나이를 2진법부터 16진법까지 어느 진법으로 읽어도 지금의 실제 나이가 되지 않으면 -1을 출력한다.

예제2

예제 1
입력
```
23 18 53
46 30 47
-1 -1 -1
```
예상 출력
```
49
-1
```
예제 2
입력
```
0 0 1
-1 -1 -1
```
예상 출력
```
1
```