题目描述

小达非常喜欢研究数学，今天他突然对斐波那契数列感兴趣了。

众所周知，斐波那契数列是这样一个数列：

$f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2)(n>=3)$

现在他对一个问题感兴趣：

满足不超过 $x$ 的最大斐波那契数是多少

因为他对不同 $x$ 的情况都感兴趣，因此会多次询问

输入格式

第一行一个 $q$ ,表示询问次数；

下面 $q$ 行，每行一个 $x$，表示一次询问。

输出格式

输出 $q$ 行，每行一个数，表示答案

3
1
5
9

1
5
8

数据规模与约定

对于$40\%$的数据，$q≤10^2,x≤10^3$

对于$80\%$的数据，$q≤10^3,x≤10^6$

对于$100$的数据，$q≤10^5, x≤10^9$