Problem N
The Easiest Problem Is This One

Some people think this is the easiest problem in today’s problem set. Some people think otherwise, since it involves sums of digits of numbers and that’s difficult to grasp.

If we multiply a number $N$ with another number $m$, the sum of digits typically changes. For example, if $m = 26$ and $N=3029$, then $N\cdot m = 78754$ and the sum of the digits is $31$, while the sum of digits of $N$ is 14.

However, there are some numbers that if multiplied by $N$ will result in the same sum of digits as the original number $N$. For example, consider $m = 37, N=3029$, then $N\cdot m = 112073$, which has sum of digits 14, same as the sum of digits of $N$.

Your task is to find the smallest positive integer $p$ among those that will result in the same sum of the digits when multiplied by $N$. To make the task a little bit more challenging, the number must also be higher than ten.

Input

The input consists of several test cases. Each case is described by a single line containing one positive integer number $N, 1\leq N\leq 100\, 000$. The last test case is followed by a line containing zero.

Output

For each test case, print one line with a single integer number $p$ which is the minimal number such that $N\cdot p$ has the same sum of digits as $N$ and $p$ is bigger than 10.

3029
4
5
42
0

37
28
28
25