Fibonacci Branch Count

In this problem, you are given a time step N and are required to calculate the number of branches on a Fibonacci Tree immediately before time step N.

The branch count is defined as follows:

• If N ≤ 1, then the result is 0.
• Otherwise, the result is the (N − 1)th Fibonacci number with the first two Fibonacci numbers defined as \(F(1)=1\) and \(F(2)=1\).

For example, for N = 4, the answer is \(F(3)=2\> since the Fibonacci sequence is 1, 1, 2, 3, ...

inputFormat

The first line contains a single integer T representing the number of test cases. Each of the following T lines contains a non-negative integer N, which represents a time step.

outputFormat

For each test case, output the number of branches on the Fibonacci Tree immediately before time step N on a new line.

## sample

3
0
1
4

0
0
2

</p>