Multiple With the Fewest Digit Types

Among the positive multiples of a natural number N, find a number whose decimal representation uses as few different digits as possible.

For example, when N = 125, the multiple 250 uses three different digits: 2, 5, and 0. Another multiple, 500, uses only two different digits: 5 and 0. Thus 500 is one of the multiples that can be written with fewer digit types.

Given N, first minimize the number of distinct digits used. If several positive multiples achieve that minimum, output the smallest such value.

The first line contains a natural number N.

N is at most 30,000.

Print the smallest positive multiple of N among the multiples that use the minimum possible number of distinct digits.