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 <= 10的1000次方。

输出

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

简单的问题，复杂的算法，好像要字符串，可又不会用字符进行加减运算，望进来的高手指点一下算法，只要算法不要程序。