Dãy số Fibonacci được định nghĩa  $$\left\{ \begin{array}{l}{F_0} = {F_1} = 1\\{F_n} = {F_{n - 1}} + {F_{n - 2}},\forall n \ge 2\end{array} \right.$$

Yêu cầu:

Cho số nguyên không âm ~n~, hãy tính ~F_n~

Input

• Dòng đầu chứa số nguyên ~T~ là số bộ test.
• Dòng sau chứa ~T~ số nguyên không âm, hai số liên tiếp cách nhau một dấu cách.

Giới hạn:

• ~0 ≤ n ≤ 10000; 1 ≤ T ≤ 100~.

Output

• Gồm ~T~ dòng là, mỗi dòng là kết quả của test đầu vào tương ứng.

Sample

Input #1

3
0 1 2

Output #1

1
1
2

Input #2

2
5 3

Output #2

8
3

Problem source: Chuyên Sơn La Online Judge