28396번 - Произведение Фибоначчи 서브태스크다국어

Напомним, что последовательность чисел Фибоначчи определяется следующим образом: $F_0 = 1$, $F_1 = 1$, $F_n = F_{n-2} + F_{n-1}$. Последовательность чисел Фибоначчи начинается так: $1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$.

Дано натуральное число $n$. Требуется посчитать количество способов представить его как произведение чисел Фибоначчи, каждое из которых больше $1$.

Первая строка ввода содержит целое число $t$ — количество тестов ($1 \le t \le 50$)

Следующие $t$ строк содержат тесты, каждая строка содержит одно целое число $n$ ($2 \le n \le 10^{18}$).

Для каждого теста вывести одно число — искомое количество способов.

В примере:

• число $2$ можно представить в виде произведения чисел Фибоначчи единственным способом $2 = 2$;
• число $7$ нельзя представить в виде произведения чисел Фибоначчи;
• число $8$ можно представить двумя способами: $8 = 2 \cdot 2 \cdot 2$ и $8 = 8$;
• число $40$ можно представить двумя способами: $40 = 2 \cdot 2 \cdot 2 · 5$ и $40 = 5 \cdot 8$.