The Fibonacci Numbers {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...} are defined by the recurrence: F(0)=0 F(1)=1 F(i)=F(i-1)+F(i-2) Write a program to calculate the Fibonacci Numbers.

The first line of the input file contains a single integer T, the number of test cases. The following T lines,each contains an integer n ( 0 <= n <= 45 ), and you are expected to calculate Fn.

Output Fn on a separate line.

Shanghai Jiaotong University Programming Contest 2004