900 - Brick Wall Patterns

假如你想用磚塊砌一面牆，考慮長度為寬度兩倍的磚塊(定義磚塊的寬度為1，長度為2，本題不需要考慮磚塊的厚度)，而牆的高度很低，等於磚塊的長度(2)，你可以用不同的磚塊排列方式把牆砌起來，所有可能的排列方式取決於牆的長度，考慮下圖說明：

• 若牆的長度為1，則只有一種排列方式。
• 若牆的長度為2，則有兩種排列方式，兩塊都直的擺或兩塊都橫著擺。
• 長度為3的牆則有3種排列方式。

若牆的長度為4可以有幾種排列方式？若為5又有幾種排列方式？

Problem

你必須寫一個程式計算當牆的長度給定之後，決定共有多少種排列方式。

Intput

你的程式會從輸入中讀取一連串的正整數，每個正整數一列表示牆的長度，最大值為50，並以0表示輸入結束。

Output

對應輸入中每列牆的長度，請輸出共有幾種排列方式。

Sample Intput

1
2
3
0

Sample Output

1
2
3

原文出處