Q580 - 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 Sample Output
4
5
0
3
8

中文翻譯:Ruby兔的ACM園地