文理学院程序设计在线练习


铺满方格

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 502   Accepted Submission(s): 220
Problem Description

有1×n的一个长方形,用1×1、1×2、1×3的骨牌铺满方格。例如当n=3时为1×3的方格(如图),此时用1×1,1×2,1×3的骨牌铺满方格,共有四种铺法。



Input

多组测试,每组一个整数n(1<=n<=50),输入到文件尾结束。

Output

每组测试输出一行,表示铺法数。

Sample Input
1
2
3
Sample Output
1
2
4