Drum Beat Sequences

You are given an integer \(n\) which represents the length of a drum beat sequence. Each beat can be either a short beat or a long beat, but two long beats cannot be consecutive.

Your task is to count the number of valid sequences of length \(n\). It can be shown that the number of valid sequences satisfies the recurrence relation:

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

with the base cases \(f(1) = 2\) and \(f(2) = 3\). For example, when \(n = 3\), the answer is \(5\).

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a single integer \(n\), the length of the drum beat sequence.

outputFormat

For each test case, output one line containing the number of valid drum beat sequences.

## sample

1
1

2

</p>