MDIGITS1 - Different Digits

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

Sample Input:
7 
15 
16 
101 
0

Sample output:
7 
555 
16 
1111

Added by:psetter
Date:2009-02-22
Time limit:0.104s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Shanghai 2004

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.