Problems
Fibonacci number
Fibonacci number
Fibonacci numbers are defined as follows:
F (1) = F (2) = 1
F (n) = F (n - 1) + F (n - 2) for n ≥ 3.
Calculate the n-th Fibonacci number.
Input
The first line specifies the number of test cases t (1 ≤ t ≤ 103
). Each of the following t lines contains a single number n (1 ≤ n ≤ 104
).
Output
For each test case output the corresponding Fibonacci number in a separate line.
Input example #1
5 1 2 3 4 5
Output example #1
1 1 2 3 5