Description
You are climbing a staircase. It takes N steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
(e.g., For n=2, there are 2 ways to reach the top:[1,1] and [2])
In this problem, there will be T testcases to check.
If you got TLE on the testcase 3 and 4, please consider using dynamic programming.
Input
The first line is T, the number of Ns.
And the following T lines are Ns, the heights of the stairs.
There are different ranges for the four test cases:
Test case 1: (1<T<20) and (1< every step N in Ns < 10)
Test case 2: (1<T<20) and (1< every step N in Ns < 45)
Test case 3&4: (1<T<=10000) and (1< every step N in Ns < 45)
Output
T solutions ended with a newline character.