斐波那契数列具有以下形式:
F1 = 1,
F2 = 2,
Fi = Fi - 1 + Fi - 2,i > 2。
让我们考虑一些由不同斐波那契数组成的非空集合 S = {s1, s2, ..., sk}。让我们求出该集合元素的值之和:
$$\sum_{i=1}^{k}s_{i}=n$$
我们将集合 S 称为数字 n 的斐波那契和分解。
很容易看出,几个数字可以分解成斐波那契和。例如,对于 13,我们有 13、5 + 8、2 + 3 + 8 — 三个分解,对于 16:3 + 13、1 + 2 + 13、3 + 5 + 8、1 + 2 + 5 + 8 — 四个分解。
由给定的数字n确定其可能的不同分解成斐波那契和的数量。
输入
第一行包含一个整数 t — 测试次数 (1 ≤ t ≤ 105)。以下 t 行中的每一行都包含一个测试。
每个测试都是一个整数 n (1 ≤ n ≤ 1018)。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。
输出
对于每个输入数据测试,在一行上打印一个数字 - 问题的答案。
示例
输入 #1
2 13 16
输出 #1
3 4
注意
如果存在第一个分解中包含但第二个分解中不包含的数字,则两次分解不同。仅被加数顺序不同的分解被认为是相等的。