Largest Fibonacci Number

You are given an integer n. Your task is to compute the largest Fibonacci number that is less than or equal to n.

The Fibonacci sequence is defined by the recurrence relation $$F_n = F_{n-1} + F_{n-2}$$ with initial terms $$F_1 = 1$$ and $$F_2 = 1$$. For a given n, find the maximum Fibonacci number \(F_k\) such that \(F_k \leq n\).

For multiple test cases, process each input and output the corresponding answer on a new line.

inputFormat

The input is given from stdin and consists of multiple test cases. The first line contains an integer T representing the number of test cases. Each of the following T lines contains a single integer n.

outputFormat

For each test case, output the largest Fibonacci number less than or equal to n on a separate line in stdout.

## sample

6
10
15
100
1
2
12

8
13
89
1
2
8

</p>