Climbing Stairs

To climb to the top of a staircase with ~N~ steps, we can take steps of one or two stairs at a time. The problem lies in finding the number of different ways we can climb to reach the top of the staircase. For example, for ~N = 3~ steps, there are ~3~ different ways: ~1-1-1~, ~2-1~, ~1-2~.

Input

A file named steps.in contains an integer ~M~ on the first line (where ~0 < M \le 1.000.000~) indicating the number of cases. Then, following are ~M~ numbers, each indicating the number ~N~ (where ~0 < N \le 50~) of steps of a staircase.

Output

A file named steps.out containing ~M~ integers (one integer per line), each indicating the number of different ways to climb for each case. The output file should end with a newline character.

Example of Input - Output Files

STDIN (steps.in)

2
4
3

STDOUT (steps.out)

5
3

Maximum execution time: ~4~.~5~ seconds