Addition Chains

For a natural number $n$, a sequence of natural numbers $\langle a_0, a_1, \ldots, a_m \rangle$ is called an addition chain for $n$ if it satisfies all four of the following conditions.

1. $a_0 = 1$
2. $a_m = n$
3. $a_0 < a_1 < a_2 < \cdots < a_{m-1} < a_m$
4. For every $k\ (1 \le k \le m)$ there exist two indices $i, j$ with $0 \le i, j \le k-1$ (they may be equal) such that $a_k = a_i + a_j$.

In other words, the first term is $1$, the last term is $n$, the sequence is strictly increasing, and every term is the sum of two earlier terms (the same term may be used twice). An addition chain with the fewest terms (that is, the smallest $m$) is called a shortest addition chain.

There can be several shortest addition chains. Among them, output the one that is lexicographically smallest. To compare two sequences lexicographically, compare their terms one by one from the front; at the first position where they differ, the sequence with the smaller value comes first.

Given several natural numbers $n$, write a program that, for each of them, finds the lexicographically smallest shortest addition chain.

The input consists of one or more test cases. Each test case is a single line containing a natural number $n$ ($1 \le n \le 100$). The last line of the input contains a single $0$, which is not processed.

For each test case, print on one line the lexicographically smallest shortest addition chain, with the terms separated by single spaces.