The Elf's Sword

Time limit1sMemory limit128 MB

Summary

For each input n, find the smallest k such that the digits 0 through 9 all appear across the multiples n, 2n, ..., kn.

Level: Easy3 of 10
Topics: Implementation, Simulation, Bit manipulation, Brute force
Solved: No attempts yet

Problem

The elves of Middle-earth believe that some numbers matter more than others. They believe that when they forge a sword from an amount $n$ of metal, choosing its thickness $k$ according to the rule below yields an extraordinarily powerful blade.

Given a non-negative integer $n$ , consider the sequence

$n,\ 2n,\ 3n,\ 4n,\ \dots,\ kn$

Writing out every number in this sequence one after another, you must find the smallest $k$ for which every digit from $0$ to $9$ appears at least once.

Elrond, Lord of Rivendell, wants a program that does this for him. Given the amount of metal $n$ , write a program that finds the ideal thickness $k$ satisfying the rule above.

Input

The input consists of several lines, each containing a single integer $n$ . Each $n$ satisfies $1 \le n \le 200{,}000{,}000$ . The input continues line by line until end of file.

Output

For each value $n$ , print on its own line the smallest $k$ such that the digits $0$ through $9$ all first appear across the sequence $n, 2n, 3n, \dots, kn$ .

Examples3

Example 1
Input
```
1
10
123456789
3141592
```
Expected output
```
10
9
3
5
```
Example 2
Input
```
1
```
Expected output
```
10
```
Example 3
Input
```
123456789
```
Expected output
```
3
```