[Poi2012]Fibonacci Representation

给出一个正整数 $x$，问 $x$ 最少能由多少个 Fibonacci 数加减算出。

例如 $1070=987+89-5-1$，因此 $x=1070$ 时答案是 $4$。

输入格式

第一行一个正整数 $q$，表示有 $q$ 组询问。

下面 $q$ 行，每行一个正整数 $x$。

输出格式

输出 $q$ 行，依次表示每组询问的答案。

样例输入

1
1070

样例输出

4

数据范围

• $q\le 10$；
• $x\le 4\times 10^{17}$。

来源与许可

本题为 POI 2012 试题「Fibonacci Representation」，题面与测试数据整理自 BZOJ 2796。

样例 1

输入

1
1070

输出

4