题目描述

Fib 数列 $0,1,1,2,3,5,8,13,21,\cdots$。

给出一个数字，用 Fib 数列各项加加减减来得到。例如：

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

输入格式

第一行一个整数 $T$ 表示数据组数。
接下来 $T$ 行，每行一个整数 $n$ 表示一个询问。

输出格式

共 $T$ 行，对于每个询问，输出最少要用多少个 Fib 数列中的数加减来得到。

1
1070

4

数据规模与约定

对于 $100\%$ 的数据，$1\leq T\leq 10$，$1\leq n\leq 10^{18}$。