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

Условие

Напомним, что последовательность чисел Фибоначчи определяется следующим образом: F₀ = 1, F₁ = 1, F_n = F_n − 2 + F_n − 1. Последовательность чисел Фибоначчи начинается так: 1, 1, 2, 3, 5, 8, 13, 21, 34, ….

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

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

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

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

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

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

Ограничения

1 ≤ t ≤ 50

2 ≤ n ≤ 10¹⁸

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

В примере:

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

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

5
2
7
8
40
64

1
0
2
2
3