无穷数列1, 1, 2, 3, 5, 8,...称为Fibonacci数列，它可以递归地定义为：
F(n)=1（对于n=0,1），F(n)=F(n-1) + F(n-2)（对于n>1）

编程实现求第n项Fibonacci数。

Input

输入有多行，每行为一个测试数据n（n为非负整数）。

Output

对于每个测试数据，输出Fibonacci数列中的第n项（可以认为不会超过32位整数的表示范围）。每个输出1行。

Sample Input

2
4
1

Sample Output

2
5
1