Description

The Fibonacci sequence is defined as follows: the first and second numbers in the sequence are both 1, and each subsequent number is the sum of the two preceding ones.
Given a positive integer a, determine the value of the a-th number in the Fibonacci sequence.

Input Format

The first line contains the number of test cases n, followed by n lines of input. Each test case consists of a single line with a positive integer a (1 ≤ a ≤ 20).

Output Format

Output n lines, each corresponding to an input. Each line should contain a positive integer representing the value of the a-th number in the Fibonacci sequence.

4
5
2
19
1

5
1
4181
1