The Easiest Problem Is This One

Write a positive integer $N$ in the decimal system as a sequence of digits.

$N = d_1 d_2 d_3 \dots d_k, \qquad 0 \le d_i \le 9.$

Each digit contributes a value multiplied by a power of $10$.

$N = d_1 \cdot 10^{k-1} + d_2 \cdot 10^{k-2} + \dots + d_{k-1} \cdot 10 + d_k = \sum_{i=0}^{k-1} d_{i+1} \cdot 10^{k-i-1}.$

The digit sum $S(N)$ is the plain sum of the digits, without multiplying by any power of $10$.

$S(N) = d_1 + d_2 + \dots + d_k = \sum_{i=0}^{k-1} d_{i+1}.$

For example, if $N = 3029$ then $S(N) = 3 + 0 + 2 + 9 = 14$.

Multiplying $N$ by another number usually changes the digit sum. For example, with $m_1 = 26$:

$N \cdot m_1 = 78754, \qquad S(N \cdot m_1) = 7 + 8 + 7 + 5 + 4 = 31.$

However, some multipliers leave the digit sum unchanged. For example, with $m_2 = 37$:

$N \cdot m_2 = 112073, \qquad S(N \cdot m_2) = 1 + 1 + 2 + 0 + 7 + 3 = 14 = S(N).$

Find the smallest positive integer $p$ that is greater than $10$ and satisfies $S(N) = S(N \cdot p)$.

The input consists of several test cases. Each test case is a single line containing one positive integer $N$, where $1 \le N \le 100\,000$. The last test case is followed by a line containing a single $0$, which is not processed.

For each test case, print on its own line the smallest integer $p$ greater than $10$ for which $S(N) = S(N \cdot p)$.