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.