Flower Planting Ways

You are given n spots in a row. You want to plant flowers such that no two adjacent spots have flowers planted. Note that not planting a flower in a spot is allowed. Your task is to determine the number of distinct ways to plant flowers following this rule.

This problem can be formulated as a recurrence relation. If you let \(f(n)\) be the number of ways to plant flowers in \(n\) spots, then:

[ f(0) = 1, \quad f(1) = 1, \quad f(n) = f(n-1) + f(n-2) \quad \text{for } n \ge 2 ]

This relation is essentially the Fibonacci sequence shifted by one index. The answer for each test case is \(f(n)\), which your program should compute using an efficient method.

inputFormat

The input is read from stdin and consists of multiple test cases. The first line contains an integer t representing the number of test cases. Each of the following t lines contains a single integer n representing the number of spots for that test case.

outputFormat

For each test case, output the number of ways to plant flowers on a separate line to stdout.

## sample

3
0
1
3

1
1
3

</p>