Migrated from Lutece 2566 土豆的数

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

土豆发现，任何一个正整数都可以拆成斐波那契数列中几个不同的正整数之和，他想知道对于任何一个正整数有多少种拆法。

斐波那契数列：$0,1,1,2,3,5,8,13,21\ldots$ （从第三项开始，每一项都等于前两项之和）

如果两种拆法中有一个数只存在于第一种拆法中而不存在第二种拆法中，则认为这两种拆法是不同的。

Input

第一行一个正整数 $T$，表示土豆想问你的正整数的个数。

接下来 $T$ 行每行一个正整数 $n$，表示土豆想问你的数。

Output

$T$ 行，每行一个数表示拆法的种数。

Samples

2
20
21

1
4

Constraints

$1\le T\le 10^5$

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

Note

$20=2+5+13$

Resources

2021 UESTC ICPC Training for Dynamic Programming