The Fibonacci word sequence of bit strings is defined as:

\[ F(n) = \begin{cases} 0 & \quad \text{if } n =0\\ 1 & \quad \text{if } n=1\\ F(n-1)+F(n-2) & \quad \text{if } n\geq 2\\ \end{cases} \]

Here denotes concatenation of strings. The first few elements are:

0 & 0 
1 & 1
2 & 10
3 & 101
4 & 10110
5 & 10110101
6 & 1011010110110
7 & 101101011011010110101
8 & 1011010110110101101011011010110110
9 & 1011010110110101101011011010110110101101011011010110101

Given a bit pattern \(p\) and a number \(n\), how often does \(p\) occur in \(F(n)\)?

INPUT The first line of each test case contains the integer \(n\) (\(0 \leq n \leq 100\)). The second line contains the bit pattern \(p\). The pattern \(p\) is nonempty and has a length of at most 100 000 characters. OUTPUT For each test case, display its case number followed by the number of occurrences of the bit pattern \(p\) in \(F(n)\). Occurrences may overlap. The number of occurrences will be less than \(2^{63}\).

SAMPLE INPUT

6
10
7
10

SAMPLE OUTPUT

Case 1: 5
Case 2: 8