Problem #2997 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

在 Microsoft 和 Google 等众多名企的笔试或面试题中出现过一道题目，计算一个泰波拿契（tribonacci）数列。

泰波拿契数列的递归定义为：

$T (0) = 0, T (1) = T (2) = 1; T (n) = T (n - 1) + T (n - 2) + T (n - 3), \forall n > 2$

根据定义，不难发现，数列的前几项为 $0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149$ 等。

现在给定一个整数 $n$ ，计算 $T (n)$ 的值。

第 1 行：一个整数 $T$ $(1 \leq T \leq 10)$ 为问题数。

接下来共 $T$ 行。每行一个整数，表示 $n$ $(0 \leq n < 37)$ 。

对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等）。

然后对应每个问题在一行中输出 $T (n)$ 的值。

Input

Output

case #0:
0
case #1:
149
case #2:
1132436852

1175 人解决，1287 人已尝试。

1416 份提交通过，共有 2724 份提交。

0.5 EMB 奖励。

创建: 11 年，10 月前.

修改: 7 年，6 月前.

最后提交: 5 天，20 小时前.

2997. 泰波拿契数列的前37项