Finding a Multiple

Interview

Time limit1sMemory limit128 MB

Summary

For each n up to 200, print the smallest multiple of n whose decimal digits are only 0 and 1, with up to 100 digits.

Level: Medium6 of 10
Topics: BFS, Number theory, Math, String matching
Solved: No attempts yet

Problem

Given a positive integer $n$ , consider a positive integer $m$ that is a multiple of $n$ and whose decimal representation consists only of the digits 0 and 1. Such an $m$ always exists. Write a program that finds the smallest such $m$ .

Here $n$ is a positive integer of at most 200, and the smallest valid $m$ has at most 100 digits.

Input

The input consists of several test cases. Each line contains one integer $n$ ( $1 \le n \le 200$ ). The last line contains $0$ and must not be processed.

Output

For each test case, print on its own line the smallest $m$ that satisfies the condition.

Examples2

Example 1
Input
```
2
6
19
0
```
Expected output
```
10
1110
11001
```
Example 2
Input
```
3
5
7
0
```
Expected output
```
111
10
1001
```