FBI #2

时间限制：1000ms

空间限制：256MB

题目背景

Monster是一个很善良的人（确信），所以他出的题都很水简单。

题目叫FBI，但是和FBI只有一丢丢关系，就是这道题和Fib数列有关。

斐波那契数列（Fibonacci sequence），又称黄金分割数列 ，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……

下文简称其为Fib数列。

在数学上，这一数列以如下递推的方法定义：$$F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N^+）$$

题目描述

假设现在你家门口又双叒叕被FBI堵门了，众所周知FBI是不会管你们家有没有门的，他们只会在1000ms的警告后冲进来。

这次的FBI更加强硬了。为了保护你家大门的安全，Monster将会给定$T$个整数$n$，而你需要在1000ms内正确回答Monster所有$T$次询问Fib数列的第$n$项是什么，然后Monster就会发动神力帮你解除FBI Warning（不是

输入格式

第一行是一个整数$T$，表示将会有$T$次询问。

接下来$T$行，每行一个数字$n$，表示Monster需要你告诉他Fib数列的第$n$项。

输出格式

输出$T$行，每行一个数字，表示$Fib[n]$，结果可能很大，注意使用合适的数据类型。

样例输入1

1
1

样例输出1

1

样例1解释

显然Fib数列的第一项是1

样例输入2

5
1
2
3
4
5

样例输出2

1
1
2
3
5

数据范围及约定

对于 $100\%$ 的数据，$1 \leq T \leq 10^6$，$1 \le n \le 90$。