Description

An integer A starts with an integer B if the string representation of B is a prefix of the string representation of A (both in decimal notation with no leading zeroes). Given an integer n, you are urged to find the smallest integer that starts with n and is divisible by every non-zero digit of n (all in decimal notation).

Input

The input for each case will consist of one integer n, and n will be between 1 and 1000000000, inclusive.

Output

The output for each case shall be the smallest integer that starts with n and is divisible by every non-zero digit of n (all in decimal notation). The result of each case should be on a separate line. The input data will be chosen so that the result will always fit in a 64 bit integer.

Sample

Input

13
648
566
1000000000
987654321
83

Output

132
648
56610
1000000000
987654321360
8304

Hint

In the first case, we need a number that starts with 13 and is divisible by 1 (always true) and by 3. The smallest one is 132.