9119 - 菲波那契数列

通过次数

23

提交次数

60

Time Limit : 1 秒
Memory Limit : 128 MB

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。给出一个正整数a,要求菲波那契数列中第a个数是多少。

Input

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1≤a≤20)。

Output

输出有n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数的大小。

Examples

Input

4
5
2
19
1

Output

5
1
4181
1

Input

4
8
2
5
4

Output

21
1
5
3

Input

9
32
35
37
38
39
40
43
45
46

Output

2178309
9227465
24157817
39088169
63245986
102334155
433494437
1134903170
1836311903

Source

用户上传