肥波纳妾

背景故事

最近不是国庆嘛，肥波曾喜欢上了一个绝世豪猫（给小蚊子戴口罩），所以决定在这中秋佳节约豪猫出来玩，不过豪猫距离肥波的位置路途遥远，豪猫在南塘镇，而肥波在狗熊岭，路途对于猫生来说，可谓是不简单，不过这难不倒机智的肥波，肥波曾发现过一个传送阵，只要写对传送阵的问题就可以打开传送锚点(😀)，可是肥波哪懂这些，现在只想快点见到绝世豪猫，聪明的你可以帮帮肥波吗？

题面

大家都知道，斐波那契数列是满足如下性质的一个数列：

• $f(1) = 1$
• $f(2) = 1$
• $f(n) = f(n-1) + f(n-2)$（$n > 2$ 且 $n$ 为整数）。

给出一个正整数 n，要求斐波那契数列中第 n 个数是多少。

输入格式

输入1个正整数$t$（t<=100）。 下面输入t行，每行一个整数x,（x<=48）;

输出格式

斐波那契数列中第 x 个数的大小

样例

4
5
2
19
1

5
1
4181
1

Limitation

1s, 1024KiB for each test case.