Divisible by Its Digits

Time limit

Memory limit

128 MB

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.