题目描述

小婷正在为珅泽教育的编程训练整理“斐波那契数列”任务，小泽负责把实际要求准确转换成程序。每一组输入都代表一次独立任务，程序必须严格遵守下面给出的规则，并按指定格式给出结果。

在核对方案时，他们发现即使任务看起来不长，边界情况、处理顺序和输出格式也同样重要。请认真阅读完整条件，帮助小泽完成这次训练。

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

给出一个正整数a，要求菲波那契数列中第a个数的结果是多少。

输入格式

第1行是测试数据的组数n，

后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1≤a≤50)。

输出格式

输出 n 行，每行一个正整数，表示对应 a 的菲波那契数 F(a)。

输入样例 #1

4
5
2
19
1

输出样例 #1

5
1
4181
1

输入样例 #2

4
1
3
5
4

输出样例 #2

1
2
5
3

输入样例 #3

6
13
8
1
17
19
4

输出样例 #3

233
21
1
1597
4181
3

数据范围

每组测试数据占1行，包括一个正整数a(1≤a≤50)。