题目描述

斐波那契数列指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 这个数列从第三项开始，每一项都等于前两项之和。

输入项数n，输出斐波那契数列第n项的值。(1<=n<=4000)

输入格式

第一行输入一个数T，表示T组输入数据 接下来T行，每组数据输入一个整数n。

输出格式

每组数据输出第n项斐波那契数列的值

3
1
2
3

1
1
2