题目描述

译自 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$。

数据范围与提示

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

子任务	分值	附加限制	子任务依赖
$1$	$15$	$2 \leq n \leq 100$
$2$	$17$	$2 \leq n \leq 10^5$	$1$
$3$	$9$	$n=2^k$对于某个$k$
$4$	$38$	$2 \leq n \leq 10^9$	$1$，$2$
$5$	$21$	$2 \leq n \leq 10^{18}$	$1$~$4$