The Fibonacci sequence is a sequence of numbers denoted as fib(n), where each number is the sum of the two preceding numbers, starting from two 1s.

The ~n~-th Fibonacci number fib(n) can be mathematically defined as follows:

~ \text{fib(n)} = \begin{cases} 1&\text{, if }n<2 \\ \text{fib(n-1) + fib(n-2)}&\text{, otherwise} \end{cases} ~

In this programming problem, you are required to write a function named fib that calculates the ~n~-th Fibonacci number and returns it as the function's output.

You can start with this template code and ensure your code can run correctly within this template:

def fib(n):
    # your code here

# Note that the following code is for local testing purposes only. You should leave this part of code unchanged and not submit it to the OJ system.
T = int(input())
for t in range(T):
    n = int(input())
    print(fib(n))

Please note that you only have to submit the definition of the fib function to the OJ system. The rest of the code is for your local testing purposes only.

Input Specification

The first line of the input gives the number of test cases, ~T~, and then ~T~ test cases follow.

For each test case, it will consist of a single line that contains an integer ~n~.

Constraints

~1 \leq T \leq 100~

~0 \leq n \leq 29~

Output Specification

For each test case, output a single line containing the value of the ~n~-th Fibonacci number.

Sample Input

2
2
5

Sample Output

2
8

Hint

recursion