[Poi2012]Fibonacci Representation

时间限制:10s      空间限制:64MB

题目描述

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

提示

没有写明提示


题目来源

没有写明来源