Description

Original source: ZOJ 1937

Given a sequence $a_0,a_1...a_m$ (where $a_0 = 1$, $a_m = n$, and $a_0 \lt a_1 \lt a_2 \lt ... \lt a_{m-1} \lt a_m$). For each $k$, it must satisfy $a_k = a_i + a_j$ ($0 \leq i, j \leq k-1$, where $i$ and $j$ can be equal).

Given the value of $n$, find the minimum value of $m$ (no need to output it) and the value of each term in such a sequence (there may be multiple valid sequences; output any one that satisfies the conditions).

Input Format

Multiple test cases, each line contains a positive integer $n$.

The input ends with $0$.

Output Format

For each test case, output a sequence of the smallest possible length that satisfies the conditions.

Sample 1

5
7
12
15
77
0

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

Constraints & Hints

$1 \leq n \leq 100,1 \leq k \leq m$