The Slower, the better??

0

0 votes
Problem

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)

Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?