서로 다른 숫자

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

요약

65536 이하의 각 n에 대해, 십진수 자리에 쓰인 서로 다른 숫자의 개수가 가장 적으면서 그런 것 중 가장 작은 n의 양의 배수를 구한다.

난이도: 어려움10점 중 8점
유형: BFS, 정수론, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

양의 정수 $n$ 이 주어졌을 때, $n$ 의 배수 중에서 그 수를 이루는 서로 다른 숫자(digit)의 개수가 가장 적은 수 $m$ 을 구하는 프로그램을 작성하시오. 예를 들어 $1334$ 를 이루는 서로 다른 숫자는 $1, 3, 4$ 로 3개이다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ 이 적힌 한 줄로 주어진다. 테스트 케이스의 개수는 $50$ 개를 넘지 않으며, $n$ 은 $65536$ 보다 작거나 같은 자연수이다. 입력의 마지막 줄에는 $0$ 이 하나 주어지며, 이는 입력의 끝을 나타낸다.

출력

각 테스트 케이스마다 위에서 정의한 $m$ 을 한 줄에 하나씩 출력한다. 조건을 만족하는 $m$ 이 여러 개인 경우에는 그중 가장 작은 값을 출력한다.

예제1

예제 1
입력
```
7
15
16
101
0
```
예상 출력
```
7
555
16
1111
```