Migrated from Lutece 1139 菲波拉契数制升级版

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

我们定义如下数列为菲波拉契数列：

$F(1)=1$

$F(2)=2$

$F(i)=F(i-1)+F(i-2) (i>=3)$

给定任意一个数，我们可以把它表示成若干互不相同的菲波拉契数之和。比如$13$有三种表示法

$13=13$

$13=5+8$

$13=2+3+8$

现在给你一个数$n$，请输出把它表示成若干互不相同的菲波拉契数之和有多少种表示法。

Input

第一样一个数$T$，表示数据组数，之后$T$行，每行一个数$n$。

$T\leq {10}^{5}$

$1\leq n\leq {10}^{18}$

Output

输出$T$行，每行一个数，即$n$有多少种表示法。

Samples

6
1
2
3
4
5
13

1
1
2
1
2
3

Resources

2015 UESTC Training for Dynamic Programming