Hello reader!

I came across this problem and I'm not sure how to approach it. Any hints would be appreciated!

Problem:

The Fibonacci sequence is defined as F(0) = 1, F(1) = 1, F(n) = F(n-1) + F(n-2). So: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Given N, count the number of ways to write N as a product of Fibonacci numbers, where each factor is > 1. Order does not matter (2×4 and 4×2 are the same representation).

Example: Input: 4 2 7 40 64 Output: 1 0 2 3

Constraints: - T ≤ 50 test cases - N can be up to 10^18

I have no idea where to start. How do you approach this kind of problem?

Thank you!