가장 쉬운 문제는 바로 이 문제

양의 정수 $N$을 십진법으로 나타내면 각 자릿수를 나열한 것이 된다.

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

각 자릿수는 $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}.$

자릿수의 합 $S(N)$은 $10$의 거듭제곱을 곱하지 않고 각 자릿수를 그대로 더한 값이다.

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

예를 들어 $N = 3029$이면 $S(N) = 3 + 0 + 2 + 9 = 14$이다.

$N$에 다른 수를 곱하면 자릿수의 합은 보통 달라진다. 예를 들어 $m_1 = 26$일 때,

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

하지만 곱해도 자릿수의 합이 변하지 않는 수도 있다. 예를 들어 $m_2 = 37$일 때,

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

$10$보다 크면서 $S(N) = S(N \cdot p)$를 만족하는 가장 작은 양의 정수 $p$를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 하나의 양의 정수 $N$이 주어지는 한 줄이며, $1 \le N \le 100\,000$이다. 마지막 테스트 케이스 다음 줄에는 $0$ 하나가 주어지고, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 $S(N) = S(N \cdot p)$를 만족하는, $10$보다 큰 가장 작은 정수 $p$를 한 줄에 하나씩 출력한다.