#2697. 「POI2012」斐波那契表示法 Fibonacci Representation

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

译自 POI 2012 Stage 2. Day 2「Rozkład Fibonacciego

给定正整数 k ,求用斐波那契数的和或差表示 k 所需要的斐波那契数数量最小值。

输入格式

第一行一个整数 p (1 \le p \le 10) 表示询问的数量。

接下来 p 行每行一个整数 k (1 \le k \le 4 \cdot 10^{17})

输出格式

对每个询问输出一个整数,表示最少需要的斐波那契数数量。

样例

样例输入

1
1070

样例输出

4