Counting Valid Strings

This problem involves counting the number of valid strings of a given length N based on a recurrence relation. Specifically, the number of valid strings is defined as follows:

For \( N = 1 \), the answer is \(2\). For \( N = 2 \), the answer is \(3\). For any \( N \ge 3 \), the recurrence is given by:

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

with initial conditions: \( dp(1) = 2 \) and \( dp(2) = 3 \). This is similar to the Fibonacci sequence, but with different base cases.

You are given several test cases. For each test case, determine the number of valid strings of length \( N \) and print the result on a new line.

inputFormat

The first line of the input contains a single integer \( T \), denoting the number of test cases. Each of the next \( T \) lines contains one integer \( N \), which represents the length of the string.

outputFormat

For each test case, output a single line containing the number of valid strings of length \( N \).

## sample

1
1

2

</p>