CF126D.Fibonacci Sums

Fibonacci numbers have the following form:

_F_1 = 1,

_F_2 = 2,

F__i = F__i - 1 + F__i - 2, i > 2.

Let's consider some non-empty set S = {_s_1, _s_2, ..., s__k}, consisting of different Fibonacci numbers. Let's find the sum of values of this set's elements:

Let's call the set S a number n's decomposition into Fibonacci sum.

It's easy to see that several numbers have several decompositions into Fibonacci sum. For example, for 13 we have 13, 5 + 8, 2 + 3 + 8 — three decompositions, and for 16: 3 + 13, 1 + 2 + 13, 3 + 5 + 8, 1 + 2 + 5 + 8 — four decompositions.

By the given number n determine the number of its possible different decompositions into Fibonacci sum.

斐波那契数具有如下形式：

$F_1 = 1$，
$F_2 = 2$，
$F_i = F_{i-1} + F_{i-2}$，其中 $i > 2$。

考虑某个非空集合 $S = \{s_1, s_2, \dots, s_k\}$，其元素均为互不相同的斐波那契数。我们计算该集合中所有元素的和：

我们将集合 $S$ 称为数 $n$ 的一个斐波那契和分解（Fibonacci sum decomposition）。

容易看出，某些数存在多个不同的斐波那契和分解。例如，对于 $13$，有 $13$、$5 + 8$、$2 + 3 + 8$ 这三种分解；而对于 $16$，则有 $3 + 13$、$1 + 2 + 13$、$3 + 5 + 8$、$1 + 2 + 5 + 8$ 这四种分解。

给定正整数 $n$，请计算其可能的不同斐波那契和分解的个数。

The first line contains an integer t — the number of tests (1 ≤ t ≤ 105). Each of the following t lines contains one test.

Each test is an integer n (1 ≤ n ≤ 1018).

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

第一行包含一个整数 $t$ —— 测试用例的数量（$1 \leq t \leq 10^5$）。接下来的 $t$ 行，每行包含一个测试用例。

每个测试用例是一个整数 $n$（$1 \leq n \leq 10^{18}$）。

请勿在 C++ 中使用 %lld 格式说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。

For each input data test print a single number on a single line — the answer to the problem.

对每组输入数据测试，在单独一行上输出一个数字——即该问题的答案。

Two decompositions are different if there exists a number that is contained in the first decomposition, but is not contained in the second one. Decompositions that differ only in the order of summands are considered equal.

如果存在一个数，它属于第一种分解但不属于第二种分解，则称这两种分解不同。仅加数顺序不同的分解被视为相同。