Divisible by Its Digits

Time limit2sMemory limit128 MB

Summary

Given N, find the smallest integer whose decimal digits start with N and that is divisible by every nonzero digit of N.

Level: Medium5 of 10
Topics: Math, Number theory, Simulation
Solved: No attempts yet

Problem

You are given a positive integer $N$ . Find the smallest integer whose decimal representation starts with $N$ and that is divisible by every nonzero digit appearing in $N$ .

Digits equal to 0 are ignored for the divisibility condition.

Input

The first line contains a positive integer $N$ .

$1 \le N \le 1,000,000,000$

Output

Print the smallest integer satisfying the condition.

Examples6

Example 1
Input
```
13
```
Expected output
```
132
```
Example 2
Input
```
648
```
Expected output
```
648
```
Example 3
Input
```
566
```
Expected output
```
56610
```
Example 4
Input
```
1000000000
```
Expected output
```
1000000000
```
Example 5
Input
```
987654321
```
Expected output
```
987654321360
```
Example 6
Input
```
83
```
Expected output
```
8304
```