Given a positive integer n, your task is to find a positive integer m, which is a multiple of n, and that m contains the least number of different digits when represented in decimal. For example, number 1334 contains three different digits 1, 3 and 4.

Input

The input consists of no more than 50 test cases. Each test case has only one line, which contains a positive integer n (1 ≤ n < 65536). There are no blank lines between cases. A line with a single 0 terminates the input.

Output

For each test case, you should output one line, which contains m. If there are several possible results, you should output the smallest one.

Example

Input:
7 
15 
16 
101 
0

Output:
7 
555 
16 
1111