Fibonacci 字串序列定义如下：

$$F(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F(n - 1) + F(n - 2) & \text{if } n \ge 2 \end{cases}$$

其中 $+$ 表示字符串的拼接。

给定一个位模式 $p$ 和一个数字 $n$，求 $p$ 在 $F(n)$ 中出现了多少次？

输入格式

输入包含多组测试数据。对于每组测试数据，第一行包含整数 $n$ ($0 \le n \le 100$)。第二行包含位模式 $p$。模式 $p$ 非空，且长度不超过 $100\,000$ 个字符。

输出格式

对于每个测试用例，输出用例编号，后跟位模式 $p$ 在 $F(n)$ 中出现的次数。出现次数可以重叠。出现次数将小于 $2^{63}$。

样例

输入格式 1

6
10
7
10
6
01
6
101
96
10110101101101

输出格式 1

Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428