算法分析与设计习题 (参考)

Q. 斐波那契数列和

单点时限: 2.0 sec

内存限制: 256 MB

斐波那契数列:

给定一个正整数 ,求有多少种方案可以把该整数分解成若干彼此不同的斐波那契数之和。

例如:

13 有三种方案:;

16 有四种方案:;

输入格式

第一行:一个整数 为问题数。
接下来 行,每行输入一个数
保证

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等)。

然后对应每个问题 , 在一行中输出方案数。

样例

Input
3
13
16
484775665757
Output
case #0:
3
case #1:
4
case #2:
117120