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

Напомним, что последовательность чисел Фибоначчи определяется следующим образом: F0=1,F1=1,Fn=Fn2+Fn1F_0 = 1, F_1 = 1, F_n = F_{n−2} + F_{n−1}. Последовательность чисел Фибоначчи начинается так: 1,1,2,3,5,8,13,21,34,1, 1, 2, 3, 5, 8, 13, 21, 34, \dots

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

Входные данные

Первая строка ввода содержит целое число tt — количество тестов (1t501 \le t \le 50) Следующие tt строк содержат тесты, каждая строка содержит одно целое число nn (2n10182 \le n \le 10^{18}).

Выходные данные

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

Подзадачи

баллынеобх. подзадачиограничения
1

15

-

2n1002 \le n \le 100

2

17

1

2n1052 \le n \le 10^5

3

9

-

n=2kn = 2k для некоторого kk

4

38

1, 2

2n1092 \le n \le 10^9

5

21

3, 4

2n10182 \le n \le 10^18

STDINSTDOUT
5
2
7
8
40
64
1
0
2
2
3

Примечание

В примере:

  • число 22 можно представить в виде произведения чисел Фибоначчи единственным способом 2=22 = 2;
  • число 77 нельзя представить в виде произведения чисел Фибоначчи;
  • число 88 можно представить двумя способами: 8=2228 = 2 \cdot 2 \cdot 2 и 8=88 = 8;
  • число 4040 можно представить двумя способами: 40=222540 = 2 \cdot 2 \cdot 2 \cdot 5 и 40=5840 = 5 \cdot 8.