Fibonacci product

The Fibonacci sequence is defined as follows: $F_0 = 1$, $F_1 = 1$, $F_n = F_{n-2} + F_{n-1}$. The sequence begins $1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$.

A natural number $n$ is given. Count the number of ways to write $n$ as a product of Fibonacci numbers, each greater than 1.

The first line contains an integer $t$, the number of test cases ($1 \le t \le 50$). Each of the next $t$ lines contains one integer $n$ ($2 \le n \le 10^{18}$).

For each test case, print the number of ways on a separate line.

In the example, the number 2 can be written as a product of Fibonacci numbers in exactly one way: $2 = 2$. The number 7 cannot be written as a product of Fibonacci numbers. The number 8 can be written in two ways: $8 = 2 \times 2 \times 2$ and $8 = 8$. The number 40 can be written in two ways: $40 = 2 \times 2 \times 2 \times 5$ and $40 = 5 \times 8$.