e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
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 n3.

Calculate the n-th Fibonacci number.

Input

The first line specifies the number of test cases t (1t103). Each of the following t lines contains a single number n (1n104).

Output

For each test case output the corresponding Fibonacci number in a separate line.

Time limit 2 seconds
Memory limit 128 MiB
Input example #1
5
1
2
3
4
5
Output example #1
1
1
2
3
5