题目描述

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

提示