Sum of Fibonacci Numbers

The Fibonacci numbers $f_k$ are defined by $f_k = f_{k-1} + f_{k-2}$ with initial values $f_0 = 0$ and $f_1 = 1$. It is well known that every positive integer can be written as a sum of one or more distinct Fibonacci numbers.

A positive integer can be written as such a sum in many ways. For example, $100$ can be written as $f_4 + f_6 + f_{11} = 3 + 8 + 89$, as $f_1 + f_3 + f_6 + f_{11} = 1 + 2 + 8 + 89$, or as $f_4 + f_6 + f_9 + f_{10} = 3 + 8 + 34 + 55$.

This problem asks you to write a positive integer as a sum of the smallest possible number of distinct Fibonacci numbers. Given a positive integer $n$, find the fewest distinct Fibonacci numbers whose sum equals $n$.

Input is read from standard input. The first line contains an integer $T$, the number of test cases. Each of the following lines contains a single integer $n$ ($1 \le n \le 1{,}000{,}000{,}000$).

Write the answer to standard output. For each test case, print the answer on its own line: the minimum number of distinct Fibonacci numbers whose sum equals $n$, listed in increasing order and separated by single spaces.