Chair Arrangement Challenge

You are given an integer N which represents the number of chairs. Your task is to determine the number of distinct arrangements of these chairs such that no two chairs are adjacent. This problem can be solved using a recurrence relation that is equivalent to the Fibonacci sequence. Formally, let \(f(N)\) be the number of arrangements. Then:

[ f(1)=1, \quad f(2)=1, \quad f(N)=f(N-1)+f(N-2) \quad \text{for} ; N\ge3 ]

The input consists of multiple test cases. For each test case, compute and output \(f(N)\). All input is provided via stdin and your output should be printed to stdout.

inputFormat

The first line contains an integer T which is the number of test cases. This is followed by T lines, each containing an integer N representing the number of chairs.

The input is read from stdin.

outputFormat

For each test case, print the number of distinct ways to arrange the chairs on a new line. The output is written to stdout.

## sample

4
1
2
3
4

1
1
2
3

</p>