# Primary X-Subfactor Series

Let $n$ be any positive
integer. A *factor* of $n$ is any number that divides evenly
into $n$, without leaving
a remainder. For example, $13$ is a factor of $52$, since $52/13 = 4$. A *subsequence* of
$n$ is a number without a
leading zero that can be obtained from $n$ by discarding one or more of its
digits. For example, $2$,
$13$, $801$, $882$, and $1324$ are all subsequences of
$8013824$, but
$214$ is not (you can’t
rearrange digits), $8334$
is not (you can’t have more occurrences of a digit than appear
in the original number), $8013824$ is not (you must discard at
least one digit), and $01$
is not (you can’t have a leading zero). A *subfactor* of
$n$ is an integer greater
than $1$ that is both a
factor and a subsequence of $n$. $8013824$ has subfactors $8$, $13$, and $14$. Some numbers do not have a
subfactor; for example, $6341$ is not divisible by
$6$, $3$, $4$, $63$, $64$, $61$, $34$, $31$, $41$, $634$, $631$, $641$, or $341$.

An x-subfactor series of $n$ is a decreasing series of integers $n_1, \ldots , n_ k$, in which (1) $n = n_1$, (2) $k \ge 1$, (3) for all $1 \le i < k$, $n_{i+1}$ is obtained from $n_ i$ by first discarding the digits of a subfactor of $n_ i$, and then discarding leading zeros, if any, and (4) $n_ k$ has no subfactor. The term “x-subfactor” is meant to suggest that a subfactor gets x’ed, or discarded, as you go from one number to the next. For example, $2004$ has two distinct x-subfactor series, the second of which can be obtained in two distinct ways. The highlighted digits show the subfactor that was removed to produce the next number in the series.

**2**004 4

200

__4__**0 0**

__20__200

__4__**00 0**

__2__The *primary* x-subfactor series has maximal length
(the largest $k$ possible,
using the notation above). If there are two or more
maximal-length series, then the one with the smallest second
number is primary; if all maximal-length series have the same
first and second numbers, then the one with the smallest third
number is primary; and so on. Every positive integer has a
unique primary x-subfactor series, although it may be possible
to obtain it in more than one way, as is the case with
$2004$.

## Input

The input consists of at most $25$ positive integers, each less than one billion, without leading zeroes, and on a line by itself. Following is a line containing only “0” that signals the end of the input.

## Output

For each positive integer, output its primary x-subfactor series using the exact format shown in the examples below.

Sample Input 1 | Sample Output 1 |
---|---|

123456789 7 2004 6341 8013824 0 |
123456789 12345678 1245678 124568 12456 1245 124 12 1 7 2004 200 0 6341 8013824 13824 1324 132 12 1 |