|
Произведение Фибоначчи
(Время: 2 сек. Память: 32 Мб Сложность: 46%)
Напомним, что последовательность чисел Фибоначчи определяется следующим образом: F0 = 1, F1 = 1, Fn = Fn-1 + Fn-2. Последовательность чисел Фибоначчи начинается так: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .
Дано натуральное число n. Требуется посчитать количество способов представить его как произведение чисел Фибоначчи, каждое из которых больше 1.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число t – количество тестов (1 ≤ t ≤ 50).
Следующие t строк содержат тесты, каждая строка содержит одно целое число n (2 ≤ n ≤ 1018).
Выходные данные
Для каждого теста в отдельной строке выходного файла OUTPUT.TXT выведите одно число – искомое количество способов.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
2
7
8
40
64 | 1
0
2
2
3 |
Пояснение к примеру
В примере:
- число 2 можно представить в виде произведения чисел Фибоначчи единственным способом: 2 = 2;
- число 7 нельзя представить в виде произведения чисел Фибоначчи;
- число 8 можно представить двумя способами: 8 = 2×2×2 и 8 = 8;
- число 40 можно представить двумя способами: 40 = 2×2×2×5 и 40 = 5×8.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
