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$.