Different Digits

Time limit1sMemory limit128 MB

Summary

For each n below 65536, find the smallest positive multiple of n whose decimal form uses the fewest distinct digits.

Level: Hard8 of 10
Topics: BFS, Dynamic programming, Number theory, Math
Solved: No attempts yet

Problem

Given a positive integer $n$ , find a positive integer $m$ that is a multiple of $n$ and, when written in decimal, contains the fewest distinct digits. If several such $m$ share this minimum number of distinct digits, output the smallest one.

For example, $1334$ contains three distinct digits: $1$ , $3$ , and $4$ .

Input

The input contains at most $50$ test cases. Each test case is a single line holding one positive integer $n$ ( $1 \le n < 65536$ ). There are no blank lines between test cases. A line containing a single $0$ terminates the input and is not processed.

Output

For each test case, print $m$ on its own line. If more than one $m$ qualifies, print the smallest. Do not print blank lines between test cases.

Examples3

Example 1
Input
```
7
15
16
101
0
```
Expected output
```
7
555
16
1111
```
Example 2
Input
```
1
2
5
9
0
```
Expected output
```
1
2
5
9
```
Example 3
Input
```
10
16
20
0
```
Expected output
```
10
16
20
```