Fibonacci 数列有如下特点：其第 1 ， 2 项均为 1 ， 1 。从第 3 个数开始，该数是其前两个数之和 . 即 :


F1=1 (n=1)
F2=1 (n=2)
Fn=Fn-1+Fn-2 (n>=3)
请你编写一个函数 fun ，它的功能是：对于一个给定的 数（ N ）， 求不大于 N 的最大 Fibonacci 数。

输入

输入的第一行是一个正整数，表示下面有几组数据需要计算。之后的每一行是一个数据 N ，其中 1 < N <= 101000 。

输出

对应输入的每一行，输出一个 不大于 N 的最大 Fibonacci 数。


要求是对大数也可以，数的范围超过c可表示的范围，可以告诉思路，也可以是代码，最好是后面的，呵呵