6796: BZOJ2796：[Poi2012]Fibonacci Representation

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

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

10=5+5

19=21-2

17=13+5-1

1070=987+89-5-1

输入格式

In the first line of the standard input a single positive integer is given （1 <=P<=10） that denotes the number of queries. The following lines hold a single positive integer K each 1<=K<=10^17.

输出格式

For each query your program should print on the standard output the minimum number of Fibonacci numbers needed to represent the number k as their sum or difference.

样例输入

1
1070

样例输出

4

提示

没有写明提示

题目来源

没有写明来源