덧셈 체인

어떤 자연수 $n$에 대하여, 다음 네 조건을 모두 만족하는 자연수 수열 $\langle a_0, a_1, \ldots, a_m \rangle$을 $n$의 덧셈 체인이라고 한다.

1. $a_0 = 1$
2. $a_m = n$
3. $a_0 < a_1 < a_2 < \cdots < a_{m-1} < a_m$
4. 모든 $k\ (1 \le k \le m)$에 대하여 $a_k = a_i + a_j$를 만족하는 두 첨자 $i, j$ ($0 \le i, j \le k-1$, $i = j$ 허용)가 존재한다.

즉, 첫 항은 $1$이고 마지막 항은 $n$이며, 수열은 순증가하고, 각 항은 앞선 두 항(같은 항을 두 번 사용해도 된다)의 합으로 만들어진다. 항의 개수가 가장 적은(즉 $m$이 최소인) 덧셈 체인을 가장 짧은 덧셈 체인이라고 한다.

가장 짧은 덧셈 체인은 여러 개일 수 있다. 그러한 체인들 중에서 사전순으로 가장 앞서는 것을 출력하라. 두 수열의 사전순 비교는 앞에서부터 항을 하나씩 비교하여, 처음으로 값이 달라지는 위치에서 더 작은 값을 가지는 수열이 앞선다고 정한다.

자연수 $n$이 여러 개 주어질 때, 각각에 대하여 가장 짧은 덧셈 체인 중 사전순으로 가장 앞서는 것을 구하는 프로그램을 작성하시오.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 자연수 $n$ ($1 \le n \le 100$)이 주어진다. 입력의 마지막 줄에는 $0$이 하나 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄에, 가장 짧은 덧셈 체인 중 사전순으로 가장 앞서는 것을 공백으로 구분하여 출력한다.