Ganesh and Sundaravel had an argument. Both argued on the speed of the processors they own. Ganesh, despite of owning an antique Pentium processor @ 500 Mhz, bravely challenged the high performing 3rd Gen Core i5 @ 3.2 Ghz of Sundaravel's Lenovo.
They both agreed on stress testing their processors with the famous 64-bit Fibanocci problem. The person with the least time of execution on a common testcase will emerge as winner.
FIbanocci numbers are defined by the following relation,
F(N) = F(N-1) + F(N-2)
Both coded a program which can give the Nth FIbanocci number given N as input. 1st Fibanocci number is 0, 2nd is 1 , 3rd is 1 and so on.
Everyone expected Sundaravel to win because of his Quad core , high speed processor. But unfortunately he lost against an antique processsor. :( His program seems to run for eternity.
Ganesh made a program which passed the testcases ,so faster than his competitor. His optimization made him win the challenge.
Now, Your job is simple, Replicate Ganesh's Program.
Input consists of T on the first line with T number of testcases which follows. Each test case consists of a number N.
Output F(N), the N th Fibanocci number for each number on a new line.
1 <= T <= 100000
1 <= F(N) <= 10^19 (1 with 19 zeros that follow)