Description

Vivid的寝室在6楼，每天都有很多机会爬楼梯，Vivid还是满乐意的，就当锻炼喽，但是Vivid的MM却不乐意。 有一次MM去Vivid的寝室，实在实在爬不动了，便出了道问题考Vivid，顺便乘机休息休息。这个问题能难倒聪明的你吗？ Vivid的寝室楼，每段楼梯有N阶台阶，MM每次爬1阶或是2阶，问爬上这N阶台阶有几种方法（先爬1阶再爬2阶和先爬2阶再爬1阶是不同的方法）

Input

这题有多个测试数据。每行有1个N（N<=25），代表楼梯的阶数。

Output

每组测试数据输出一个整数表示爬上这N阶台阶的方法数。

Sample

Input

1
2
3

Output

1
2
3

Source: vivid