| Codeforces Beta Round 93 (Div. 1 Only) |
|---|
| Закончено |
Числа Фибоначчи имеют следующий вид:
Рассмотрим какое-либо непустое множество S = {s1, s2, ..., sk}, состоящее из различных чисел Фибоначчи, и найдем сумму значений элементов этого множества:
Будем называть множество S разложением в фибоначчиеву сумму числа n.
Нетрудно видеть, что некоторые числа имеют несколько разложений в фибоначчиеву сумму. Например, для 13 имеем 13, 5 + 8, 2 + 3 + 8 — три разложения, а для 16: 3 + 13, 1 + 2 + 13, 3 + 5 + 8, 1 + 2 + 5 + 8 — четыре разложения.
По заданному числу n определите количество его различных разложений в фибоначчиеву сумму.
В первой строке находится целое число t — количество тестов (1 ≤ t ≤ 105). В каждой из последующих t строк находится по одному тесту.
Каждый тест — это целое число n (1 ≤ n ≤ 1018).
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Для каждого теста из входных данных выведите одно число в отдельной строке — ответ на задачу.
2
13
16
3
4
Два разложения различны если существует число, которое содержится в одном разложении, и не содержится в другом. Разложения, отличающиеся только порядком слагаемых, считаются одинаковыми.
