Count Ways to Climb Ladders

You are given a series of ladders, each with a number of steps. For each ladder, you may climb either 1 or 2 steps at a time. Your task is to compute the number of distinct ways to climb each ladder.

The recurrence relation to compute the number of ways is given by:

$$f(n)=f(n-1)+f(n-2)$$

with the base cases:

$$f(0)=1,\quad f(1)=1$$

Example: For a ladder with 4 steps, the number of ways is 5.

inputFormat

The input consists of two lines. The first line contains a single integer (T) representing the number of ladders. The second line contains (T) space-separated integers, where each integer (n_i) represents the number of steps in the (i)-th ladder.

outputFormat

Output (T) integers separated by spaces. The (i)-th integer should be the number of distinct ways to climb the ladder with (n_i) steps.## sample

1
2

2