Fibonacci Representation

The Fibonacci sequence is a sequence of integers, called Fibonacci numbers, defined by:

• $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-2} + F_{n-1}$ for $n > 1$.

Its first terms are $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$

Byteasar studies how integers can be written as sums and differences of Fibonacci numbers. Right now he wants the minimum representation: one that uses the fewest Fibonacci numbers, for a given positive integer $k$. The same Fibonacci number may be used more than once. For example, $10$, $19$, $17$, and $1070$ can be written with as few as $2$, $2$, $3$, and $4$ Fibonacci numbers, respectively:

• $10 = 5 + 5$
• $19 = 21 - 2$
• $17 = 13 + 5 - 1$
• $1070 = 987 + 89 - 5 - 1$

Write a program that, for a given positive integer $k$, finds the minimum number of Fibonacci numbers whose signed sum (using additions and subtractions) equals $k$.

The first line contains a single positive integer $p$ ($1 \le p \le 10$), the number of queries. Each of the next $p$ lines contains one positive integer $k$ ($1 \le k \le 4 \cdot 10^{17}$).

For each query, print on its own line the minimum number of Fibonacci numbers needed to represent $k$ as their sum or difference.