Nth Term Sequence

Problem Description:

We define a sequence by the recurrence relation:
(a_1 = 1,\ a_2 = 2) and (a_n = a_{n-1} + a_{n-2}) for (n \ge 3).

Your task is to compute the (n^{th}) term of this sequence for multiple test cases. The recurrence is similar to the Fibonacci sequence, but with different initial values. Use the relation to generate the (n^{th}) term for each test case provided.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (T) indicating the number of test cases. Each of the following (T) lines contains a single integer (n), representing the position in the sequence for which you must compute (a_n).

outputFormat

Output the nth term of the sequence for each test case on a separate line using standard output (stdout).## sample

3
1
2
5

1
2
8