Description

有一些整数N（N≤46），输出以这些整数为序数的第n项fibonacci数。文件中的数据可能上万，但要求运行时间不超过1秒钟。

Sample

Input

5
6
7
8
9
40

Output

5
8
13
21
34
102334155