Fibonacci numbers have the following form:

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.

The first line contains an integer *t* — the number of tests (1 ≤ *t* ≤ 10^{5}). Each of the following *t* lines contains one test.

Each test is an integer *n* (1 ≤ *n* ≤ 10^{18}).

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.

提交代码