1755:菲波那契數列

總時間限制: 1000ms 記憶體限制: 65536kB

描述

菲波那契數列是指這樣的數列: 數列的第一個和第二個數都為1，接下來每個數都等于前面2個數之和。

給出一個正整數a，要求菲波那契數列中第a個數是多少。

輸入

第1行是測試資料的組數n，後面跟着n行輸入。每組測試資料占1行，包括一個正整數a(1 <= a <= 20)

輸出

輸出有n行，每行輸出對應一個輸入。輸出應是一個正整數，為菲波那契數列中第a個數的大小

樣例輸入

4

5

2

19

1

樣例輸出

4181

斐波那契數列代碼很多人的遞歸寫法如下：

這個沒什麼太大的問題，隻是在多組測試資料的情況下，下面的寫法會比較好。