问题描述

设 $n$ 为任意正整数。$n$ 的一个因数是能够整除 $n$ 且不留余数的数。例如，$13$ 是 $52$ 的因数，因为 $52/13 = 4$。$n$ 的一个子序列是指通过删除 $n$ 中的一个或多个数字（不重新排列数字）且没有前导零的数。例如，$2$、$13$、$801$、$882$ 和 $1324$ 是 $8013824$ 的子序列，但 $214$ 不是（不能重新排列数字），$8334$ 不是（不能比原数字中某数字的出现次数更多），$8013824$ 不是（必须至少删除一个数字），$01$ 不是（不能有前导零）。$n$ 的一个子因数是指大于 $1$ 的整数，它既是 $n$ 的因数，又是 $n$ 的子序列。$8013824$ 的子因数有 $8$、$13$ 和 $14$。有些数没有子因数；例如，$6341$ 不能被 $6$、$3$、$4$、$63$、$64$、$61$、$34$、$31$、$41$、$634$、$631$、$641$ 或 $341$ 整除。

$n$ 的一个 $x$-子因数序列是一个递减的整数序列 $n_1, \ldots, n_k$，满足以下条件：

1. $n = n_1$，
2. $k \geq 1$，
3. 对于所有 $1 \leq i < k$，$n_{i+1}$ 是通过先删除 $n_i$ 的一个子因数的数字，然后删除前导零（如果有）得到的，
4. $n_k$ 没有子因数。

术语“$x$-子因数”表示在从 $n_i$ 到 $n_{i+1}$ 的过程中，一个子因数被“划掉”或删除。例如，$2004$ 有两个不同的 $x$-子因数序列，其中第二个序列可以通过两种不同的方式得到。被高亮显示的数字表示为产生序列中的下一个数字而删除的子因数。

• $2004$ $4$
• $2004$ $200$ $0$
• $2004$ $200$ $0$

主 $x$-子因数序列是长度最大的序列（使用上述符号，即最大的 $k$）。如果有两个或多个最大长度的序列，则选择第二个数字最小的序列作为主序列；如果所有最大长度的序列的第一和第二个数字都相同，则选择第三个数字最小的序列作为主序列；以此类推。每个正整数都有一个唯一的主 $x$-子因数序列，尽管可能存在多种方式得到它，就像 $2004$ 的情况一样。

输入

输入由一个或多个正整数组成，每个数小于十亿，没有前导零，且每行一个。接下来是一行只包含“$0$”的行，表示输入结束。

输出

对于每个正整数，按照示例中的格式输出其主 $x$-子因数序列。

示例输入 1

123456789
7
2004
6341
8013824
0

示例输出 1

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

来源

Mid-Central USA 2004