Minimum Coins with Fibonacci-like Values

You are given a target integer \(N\). You have an unlimited supply of coins whose values come from a Fibonacci-like sequence defined by \(F(1)=1\), \(F(2)=2\), and for \(n \ge 3\), \(F(n)=F(n-1)+F(n-2)\). However, when generating the sequence, only values \(\le N\) are included.

Your task is to select coins (possibly using the same coin value multiple times) so that their total value is at least \(N\) while minimizing the number of coins used. A greedy strategy that chooses the largest possible coin at each step is sufficient.

For example, if \(N=10\), the Fibonacci-like sequence is \(\{1,2,3,5,8\}\). The optimal strategy is to pick coin \(8\) and then coin \(2\), giving a total of \(10\) with 2 coins.

inputFormat

The first line of input contains a single integer \(T\) (\(1 \le T \le 10^5\)) representing the number of test cases. Each of the following \(T\) lines contains one integer \(N\) (\(1 \le N \le 10^9\)), the target value.

outputFormat

For each test case, output a single line containing the minimum number of coins required such that their total value is at least \(N\).

## sample

1
10

2

</p>