【漸化式】 3項間漸化式 2 (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

整数 Q と Q 個の整数 k_1, k_2, ... , k_Q が与えられます。

次のように定められた数列の k_i 項目の値を順に出力してください。

ちなみに、これはフィボナッチ数列と呼ばれる有名な数列です。

・ a_1 = 1 
・ a_2 = 1 
・ a_n = a_{n-2} + a_{n-1} (n ≧ 3)

入力される値

Q
k_1
k_2
...
k_Q

・ 1行目では、2行目以降で与えられる入力の行数 Q が与えられます。

・続く Q 行のうち i 行目では、k_i が与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

Q 行出力してください。

i 行目には、数列の k_i 項目の値を出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

a_{k_1}
a_{k_2}
...
a_{k_Q}

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ Q ≦ 100

・ 1 ≦ k_i ≦ 40 (1 ≦ i ≦ Q)