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