← 返回题目列表

Codeforces · 126/D

D. 斐波那契和

中文机器翻译题面 查看原题

斐波那契数列具有以下形式:

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

注意

如果存在第一个分解中包含但第二个分解中不包含的数字,则两次分解不同。仅被加数顺序不同的分解被认为是相等的。