Minimum Fibonacci Sum Representation

You are given an integer x. In this problem, the Fibonacci sequence is defined in a nontraditional manner as:

\(F_1 = 1, F_2 = 2, \text{ and } F_n = F_{n-1} + F_{n-2}\) for \(n \ge 3\).

Your task is to determine the minimum number of Fibonacci numbers (from this sequence) whose sum equals x. This problem can be solved using a greedy algorithm: always subtract the largest Fibonacci number less than or equal to the remaining value.

For example, if x = 14, the Fibonacci numbers up to 14 are [1, 2, 3, 5, 8, 13]. Using a greedy approach, we choose 13 (\(14-13 = 1\)) and then 1, yielding a total count of 2.

inputFormat

The first line contains a single integer T denoting the number of test cases. Each of the following T lines contains one integer x.

Input is given via stdin.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of Fibonacci numbers required to sum up to x.

Output should be printed to stdout.

## sample

2
4
10

2
2

</p>