Fibonacci Sequence Calculator

Given a positive integer \(n\), compute the \(n\)-th term of the Fibonacci sequence. The Fibonacci sequence is defined as follows:

\(F(1)=1,\quad F(2)=1,\quad F(n)=F(n-1)+F(n-2)\) for \(n>2\).

You are provided with multiple test cases. For each test case, output the \(n\)-th Fibonacci number on a new line.

inputFormat

The input is given via standard input.

The first line contains a single integer \(T\), the number of test cases. Each of the following \(T\) lines contains one integer \(n\), representing the test case.

outputFormat

For each test case, output a single line containing the \(n\)-th Fibonacci number.

## sample

5
1
2
3
4
5

1
1
2
3
5

</p>