Given an integer N, find the Nth number in the fibonacci series. Consider 0 and 1 to be the seed values. In a fibonacci series, each number ( Fibonacci number ) is the sum of the two preceding numbers. The series with 0 and 1 as seed values will go like- 0, 1, 1, 2, 3, 5… .

Input

The first line contains an integer T, depicting total number of test cases. Then following T lines contains an integer N.

Constraints:

1 ≤ T ≤ 50

1 ≤ N ≤ 50

Output

Space separated Nth fibonacci number for each N given in the input