피보나치 수의 합

피보나치 수 $f_k$는 $f_k = f_{k-1} + f_{k-2}$로 정의되며, 초기값은 $f_0 = 0$, $f_1 = 1$이다. 모든 양의 정수는 서로 다른 피보나치 수 하나 이상의 합으로 나타낼 수 있다는 사실이 잘 알려져 있다.

한 양의 정수를 서로 다른 피보나치 수들의 합으로 나타내는 방법은 여러 가지다. 예를 들어 $100$은 $f_4 + f_6 + f_{11} = 3 + 8 + 89$로도, $f_1 + f_3 + f_6 + f_{11} = 1 + 2 + 8 + 89$로도, $f_4 + f_6 + f_9 + f_{10} = 3 + 8 + 34 + 55$로도 나타낼 수 있다.

이 문제는 한 양의 정수를 개수가 가장 적은 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 양의 정수 $n$이 주어질 때, 합이 $n$과 같아지면서 사용하는 서로 다른 피보나치 수의 개수가 최소가 되는 조합을 구하라.

입력은 표준 입력으로 받는다. 첫 번째 줄에 테스트 데이터의 개수를 나타내는 정수 $T$가 주어진다. 이어지는 각 줄에는 정수 $n$이 하나씩 주어진다 ($1 \le n \le 1{,}000{,}000{,}000$).

출력은 표준 출력을 사용한다. 각 테스트 데이터마다 답을 한 줄에 출력한다. 합이 주어진 정수 $n$과 같아지는 최소 개수의 서로 다른 피보나치 수들을 증가하는 순서로 공백으로 구분하여 출력한다.