Now that he has grown up,Bit boy can climb atmost N steps at a time. Given the number of steps find the number of ways that he can climb the steps.
Input Format
First line of test case contains T , number of testcases. next T lines contains N , Number of steps.
Output Format
Print Answer for each test case in a newline
Constraints
1<=T<=100 1<=N<=500
Sample Input
2
1
2 Sample Output
1
2
2^(n-1) is the answer because simply either you come from the back ones or climb directly to the n steps
which is f(n) = f(n-1) + f(n-2) + f(n-3) ... + f(1) + 1 which we can simply deduce that it is 2 ^ (n-1)
f(n) = f(n-1) + f(n-2) + ... + f(1) + 1
f(n-1) = f(n-2) + f(n-3) +... + f(1) + 1
f(n) -f(n-1) = f(n-1)
f(n) = 2f(n-1)
and since f(1) = 1 then f(n) = 2^(n-1)*f(1) = 2^(n-1)
it also can be solved by an n^2 dynamic programming which is kinda bad
Thanks.