#2796. [POI2012] Fibonacci Representation

[POI2012] Fibonacci Representation

题目描述

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

给出一个数字,用 Fib 数列各项加加减减来得到。例如:

  • 10=5+510=5+5
  • 19=21219=21-2
  • 17=13+5117=13+5-1
  • 1070=987+89511070=987+89-5-1

输入格式

第一行一个整数 TT 表示数据组数。
接下来 TT 行,每行一个整数 nn 表示一个询问。

输出格式

TT 行,对于每个询问,输出最少要用多少个 Fib 数列中的数加减来得到。

1
1070
4

数据规模与约定

对于 100%100\% 的数据,1T101\leq T\leq 101n10181\leq n\leq 10^{18}