[AdditionalFile2697.zip](file://AdditionalFile2697.zip?type=additional_file)

#2697. 「POI2012 R2」斐波那契表示法 Fibonacci Representation

标签: 传统 | 时间限制: 100 ms | 内存限制: 64 MiB |

题目描述

译自 POI 2012 Stage 2. Day 2「Rozkład Fibonacciego」

给定正整数 $k$，求用斐波那契数的和或差表示 $k$ 所需要的斐波那契数数量最小值。

输入格式

第一行一个整数 $p (1 \le p \le 10)$ 表示询问的数量。

接下来 $p$ 行每行一个整数 $k (1 \le k \le 4 \cdot 10^{17})$。

输出格式

对每个询问输出一个整数，表示最少需要的斐波那契数数量。

样例

输入

1
1070

输出

4