[AdditionalFile4313.zip](file://AdditionalFile4313.zip?type=additional_file)

#4313. 「ROIR 2023 Day1」斐波那契乘积

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI Regional 2023 Day1 T2. Произведение Фибоначчи

我们知道，斐波那契数列定义如下：$F_{0}=1, F_{1}=1, F_{n}=F_{n-2}+F_{n-1}$。斐波那契数列的前几项是：$1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$

给定一个自然数 $n$。需要计算有多少种方法可以将其表示为多个大于 $1$ 的斐波那契数的乘积。

输入格式

输入包含多组数据。第一行包含一个整数 $t$ $(1 \le t \le 50)$，表示输入数据组数。

接下来的 $t$ 行中，每行包含一个整数 $n$ $(2 \leq n \leq 10^{18})$。

输出格式

对于每组输入数据，输出一个整数，表示表示方法的数量。

样例

输入

5
2
7
8
40
64

输出

1
0
2
2
3

在样例中：

• 数字 $2$ 只能表示为 $2=2$；
• 数字 $7$ 不能表示为斐波那契数的乘积；
• 数字 $8$ 有两种表示方法：$8=2 \cdot 2 \cdot 2$ 和 $8=8$；
• 数字 $40$ 有两种表示方法：$40=2 \cdot 2 \cdot 2 \cdot 5$ 和 $40=5 \cdot 8$。

数据范围与提示

详细子任务附加限制及分值如下表所示。