斐波那契数列是一串整数，称为斐波那契数，定义如下：

• $\text{Fib}_{0}=0$, $\text{Fib}_{1}=1$, $\text{Fib}_{n}=\text{Fib}_{n-2}+\text{Fib}_{n-1}$，其中 $n > 1$

其初始元素为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Byteasar 正在研究将数字表示为斐波那契数之和或之差的方法。目前他想知道对于给定的正整数 $k$，其最小表示法是什么，即使用最少数量（不一定互不相同）的斐波那契数来表示该数。例如，数字 10、19、17 和 1070 的最小表示法分别需要 2、2、3 和 4 个斐波那契数，如下所示：

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

请帮助 Byteasar！编写一个程序，对于给定的正整数 $k$，确定将其表示为斐波那契数之和或之差所需的最少斐波那契数个数。

输入格式

标准输入的第一行包含一个正整数 $p$ ($1 \le p \le 10$)，表示询问次数。接下来的 $p$ 行，每行包含一个正整数 $k$ ($1 \le k \le 4\cdot 10^{17}$)。

输出格式

对于每次询问，程序应在标准输出中打印将数字 $k$ 表示为斐波那契数之和或之差所需的最少斐波那契数个数。

样例

输入 1

1
1070

输出 1

4