Напомним, что последовательность чисел Фибоначчи определяется следующим образом: . Последовательность чисел Фибоначчи начинается так:
Дано натуральное число . Требуется посчитать количество способов представить его как произведение чисел Фибоначчи, каждое из которых больше .
Входные данные
Первая строка ввода содержит целое число — количество тестов () Следующие строк содержат тесты, каждая строка содержит одно целое число ().
Выходные данные
Для каждого теста вывести одно число — искомое количество способов
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 15 | - | |
2 | 17 | 1 | |
3 | 9 | - | для некоторого |
4 | 38 | 1, 2 | |
5 | 21 | 3, 4 |
STDIN | STDOUT |
5 2 7 8 40 64 | 1 0 2 2 3 |
Примечание
В примере: