P10095 [ROIR 2023] Fibonacci Product (Day 1)

Translated from [ROIR 2023 D1T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。 A Fibonacci number refers to a number appearing in the Fibonacci sequence ($f_0=1,f_1=1,f_i=f_{i-2}+f_{i-1}$)。

Given a natural number $n$, find the number of ways to represent it as a product of several Fibonacci numbers greater than $1$。

The first line contains an integer $t$, representing the number of test cases。 The next $t$ lines each contain one integer $n$。

For each test case, output one integer representing the answer。

Explanation of the samples: - $2=2$。 - $7$ cannot be represented as a Fibonacci product。 - $8=8=2\times2\times2$。 - $40=5\times8=2\times2\times2\times5$。 - $64=8\times8=2\times2\times2\times8=2\times2\times2\times2\times2\times2$。 This problem uses bundled testdata。 | Subtask ID | Score | $2\le n\le$ | | :----------: | :----------: | :----------: | | $1$ | $15$ | $100$ | | $2$ | $17$ | $10^5$ | | $3$ | $9$ | $n$ is an integer power of $2$ | | $4$ | $38$ | $10^9$ | | $5$ | $21$ | $10^{18}$ | For all testdata, $1\le t\le50$，$2\le n\le10^{18}$。 Translated by ChatGPT 5