Description

已知菲波那契数的定义： f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) n>1的整数 根据输入数据中的n，输出第n项菲波那契数。

Input

输入数据中含有一些整数n（0≤n≤46）。

Output

根据每个整数n，输出其第n项菲波那契数，每个数占独立一行。

Sample

Input

5
6
7
8
9
40

Output

5
8
13
21
34
102334155

Source: qianneng