580 - Critical Mass

曼哈頓計劃初期，人們並不確切知道放射性物質的危險性，大量的工廠被建造出來提煉鈾原料與鈽原料，這些放射性物質的半成品混合物與完成品被裝在金屬 桶子、玻璃瓶或紙箱中，且被放置在水泥地板的儲藏室內。工人們並不清楚他們可能會被這些放射性物質所感染，甚致引起核反應。知道事情嚴重性的工廠高階主管認為只要照著物理學家的建議，避免混合過量到足以達到臨界質量的放射性物質，就可以避免災難發生。但事情並非這麼簡單，因為人們總是會犯錯，不知道事情嚴重性的工人們粗心大意地處理核物質，過量推積可能誘發核反應的原料，災難隨時可能發生，

幸運的是，有物理學家發現事情的嚴重性，他們制定工作守則來避免過量堆積可能引發臨界反應的核物質。放置鈾塊的方法很簡單，以"U"表示鈾塊，以"L"表 示鉛塊，鈾塊與鉛塊交互堆疊，鈾塊不能連續疊超過兩個，藉由這種方式可以避免鈾塊引發臨界反應(連續三個鈾塊疊在一起可能會達到臨界質量)。另外， 一堆鈾、鉛塊的高度不會超過30個，因為樓層的高度最多只能疊30個。

其中有一位物理學家對此解決方案還是感到不安，他認為工人們還是可能因為粗心、教育訓練不足…等等原因導致核反應發生。他提出一個問題：工人以隨機的方式堆疊放射性鈾塊與非放射性鉛塊，使高度達到 n 塊，共有幾種可能的排列組合方式使得危險再次發生？

例如假設堆疊高度為3，則只有一種可能的組合的方式使鈾塊連續疊超過兩個：
1: UUU


若堆疊高度為4，則共有3種可能的組合方式：
1: UUUL
2: LUUU
3: UUUU

Input

輸入的每一列都有一個整數 n，每個整數表示堆疊的最大高度，0 < n <= 30。當 n = 0 表示測試資料結束。

Output

針對每組測試資料，請輸出共有幾種不同的危險組合方式。

Sample Input 

4
5
0

Sample Output 

3
8

---

原文出處