P3539 [POI 2012] ROZ-Fibonacci Representation

**译自 POI 2012 Stage 2. Day 2「[Rozkład Fibonacciego](https://szkopul.edu.pl/problemset/problem/w1QbhPufazp-sH6X-u4pTnNu/site/?key=statement)」** 给定正整数 $k$，求用斐波那契数的和或差表示 $k$ 所需要的斐波那契数数量最小值，例如： - $10=5+5$ - $19=21-2$ - $17=13+5-1$ - $1070=987+89-5-1$

第一行一个整数 $p (1 \le p \le 10)$ 表示询问的数量。 接下来 $p$ 行每行一个整数 $k (1 \le k \le 4 \cdot 10^{17})$。

对每个询问输出一个整数，表示最少需要的斐波那契数数量。 翻译来自于 [LibreOJ](https://loj.ac/p/2697)。