Произведение Фибоначчи

시간 제한1초메모리 제한1024 MB

요약

주어진 n을 1보다 큰 피보나치 수의 곱으로 나타내는 방법의 수를 센다.

난이도: 보통10점 중 7점
유형: 정수론, 동적 계획법, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

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

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

입력

Первая строка ввода содержит целое число $t$ — количество тестов ( $1 \le t \le 50$ )

Следующие $t$ строк содержат тесты, каждая строка содержит одно целое число $n$ ( $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 · 5$ и $40 = 5 \cdot 8$ .

예제1

예제 1
입력
```
5
2
7
8
40
64
```
예상 출력
```
1
0
2
2
3
```