Define \(F_0=0\), \(F_1=1\), and \(F_n=F_{n-1}+F_{n-2}\) for \(n>=2\). Answer the given queries.

Input

The first line contains \(T\). Each of the next \(T\) lines contains \(n\).

The input satisfies:

• \(1 \le T \le 100\)
• \(0 \le n \le 92\)

Output

For each query, print \(F_n\) on its own line.

Example

Input

100
56
67
81
42
29
5
47
30
38
65
31
47
26
4
77
41
10
1
75
40
27
9
25
22
36
17
77
31
52
82
78
16
92
85
17
16
42
92
63
7
49
74
21
72
20
18
87
22
22
12
16
38
5
13
34
64
6
80
46
46
12
83
70
23
64
85
14
12
1
11
26
87
36
86
56
62
17
64
63
76
38
24
6
41
83
13
54
29
73
60
1
46
1
66
40
61
50
43
85
15

Output

225851433717
44945570212853
37889062373143906
267914296
514229
5
2971215073
832040
39088169
17167680177565
1346269
2971215073
121393
3
5527939700884757
165580141
55
1
2111485077978050
102334155
196418
34
75025
17711
14930352
1597
5527939700884757
1346269
32951280099
61305790721611591
8944394323791464
987
7540113804746346429
259695496911122585
1597
987
267914296
7540113804746346429
6557470319842
13
7778742049
1304969544928657
10946
498454011879264
6765
2584
679891637638612258
17711
17711
144
987
39088169
5
233
5702887
10610209857723
8
23416728348467685
1836311903
1836311903
144
99194853094755497
190392490709135
28657
10610209857723
259695496911122585
377
144
1
89
121393
679891637638612258
14930352
420196140727489673
225851433717
4052739537881
1597
10610209857723
6557470319842
3416454622906707
39088169
46368
8
165580141
99194853094755497
233
86267571272
514229
806515533049393
1548008755920
1
1836311903
1
27777890035288
102334155
2504730781961
12586269025
433494437
259695496911122585
610