Задача 2. Произведение Фибоначчи ≡

Условие

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

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

Формат входных данных

Первая строка ввода содержит целое число $t$ — количество тестов.

Следующие $t$ строк содержат тесты, каждая строка содержит одно целое число $n$.

Формат выходных данных

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

Ограничения

$1 \le t \le 50$

$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 \cdot 5$ и $40 = 5\cdot 8$.

Примеры тестов

5
2
7
8
40
64

1
0
2
2
3