Fibonacci number#2292
Sign in

Fibonacci number

2 seconds
128 megabytes
Easy

The Fibonacci numbers are defined as follows:

F(1) = 1 , \\ F(2) = 1, \\ F(n) = F(n-1) + F(n-2), n \ge 3.

Compute the -th Fibonacci number.

Input

The first line contains the number of test cases t~(1 \le t \le 10^3). Each of the next lines contains one integer n~(1 \le n \le 10^4).

Output

For each test case, print the corresponding Fibonacci number on a separate line.

Examples

Example 1

Loading
Loading