서로 다른 숫자

시간 제한1초메모리 제한128 MB

요약

65536 미만의 각 n에 대해, 십진수로 표현했을 때 서로 다른 숫자의 개수가 가장 적은 n의 최소 양의 배수를 구한다.

난이도: 어려움10점 중 8점
유형: BFS, 동적 계획법, 정수론, 수학
정답자: 아직 제출이 없습니다

문제

양의 정수 $n$ 이 주어질 때, $n$ 의 배수이면서 십진법으로 나타냈을 때 서로 다른 숫자(digit)의 종류가 가장 적은 양의 정수 $m$ 을 구하세요. 서로 다른 숫자의 종류 수가 최소인 $m$ 이 여러 개라면, 그중 값이 가장 작은 것을 출력합니다.

예를 들어 $1334$ 는 $1$ , $3$ , $4$ 의 서로 다른 세 가지 숫자를 포함합니다.

입력

입력은 최대 $50$ 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 한 줄에 하나의 양의 정수 $n$ ( $1 \le n < 65536$ )을 담고 있습니다. 테스트 케이스 사이에는 빈 줄이 없습니다. 한 줄에 $0$ 하나만 있는 줄이 나오면 입력이 끝나며, 그 줄은 처리하지 않습니다.

출력

각 테스트 케이스마다 $m$ 을 한 줄에 출력합니다. 조건을 만족하는 $m$ 이 여러 개이면 가장 작은 것을 출력합니다. 테스트 케이스 사이에는 빈 줄을 출력하지 않습니다.

예제3

예제 1
입력
```
7
15
16
101
0
```
예상 출력
```
7
555
16
1111
```
예제 2
입력
```
1
2
5
9
0
```
예상 출력
```
1
2
5
9
```
예제 3
입력
```
10
16
20
0
```
예상 출력
```
10
16
20
```