Background

Translated from ROIR 2023 D1T2。

A Fibonacci number refers to a number appearing in the Fibonacci sequence ($f_0=1,f_1=1,f_i=f_{i-2}+f_{i-1}$)。

Problem Description

Given a natural number $n$, find the number of ways to represent it as a product of several Fibonacci numbers greater than $1$。

Input Format

The first line contains an integer $t$, representing the number of test cases。

The next $t$ lines each contain one integer $n$。

Output Format

For each test case, output one integer representing the answer。

5
2
7
8
40
64

1
0
2
2
3

Hint

Explanation of the samples:

• $2=2$。
• $7$ cannot be represented as a Fibonacci product。
• $8=8=2\times2\times2$。
• $40=5\times8=2\times2\times2\times5$。
• $64=8\times8=2\times2\times2\times8=2\times2\times2\times2\times2\times2$。

This problem uses bundled testdata。

For all testdata, $1\le t\le50$，$2\le n\le10^{18}$。

Translated by ChatGPT 5