Fast Fibonacci

Introduction

The Fibonacci Sequence is really well known. In fact, it even has it's own day on November 23rd.
Unfortunately as the sequence goes up higher and higher, the time it takes to solve increases exponentially. That is if you don't do any tricks!

Write a program that can quickly determine the $n$th Fibonacci number in the sequence.

Input

The first line of input is $T$, the number of test cases. Each test case consists of one line containing $n$, the term of the sequence to generate, where $1 \leq n \leq 100$.

3
4
10
20


Output

Output the $n$th term in the Fibonacci Sequence.

3
55
6765