Given an integer `k`

, *return the minimum number of Fibonacci numbers whose sum is equal to *`k`

. The same Fibonacci number can be used multiple times.

The Fibonacci numbers are defined as:

`F`

_{1}= 1`F`

_{2}= 1`F`

for_{n}= F_{n-1}+ F_{n-2}`n > 2.`

`k`

.

**Example 1:**

Input:k = 7Output:2Explanation:The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... For k = 7 we can use 2 + 5 = 7.

**Example 2:**

Input:k = 10Output:2Explanation:For k = 10 we can use 2 + 8 = 10.

**Example 3:**

Input:k = 19Output:3Explanation:For k = 19 we can use 1 + 5 + 13 = 19.

**Constraints:**

`1 <= k <= 10^9`

class Solution {
public int findMinFibonacciNumbers(int k) {
}
}