beecrowd | 1432

Triple-Free Binary Strings

By Rujia Liu, TU China
Timelimit: 3

A binary string consists of ones and zeros. Given a binary string T, if there is no binary string S such that SSS (concatenate three copies of S together) is a substring of T, we say T is triple-free.

A pattern consists of ones, zeros and asterisks, where an asterisk (*) can be replaced by either one or zero. For example, the pattern 0**1 contains strings 0001, 0011, 0101, 0111, but not 1001 or 0000.

Given a pattern P, how many triple-free binary strings does it contain?

Input

Each line of the input represents a test case, which contains the length of the pattern N (1 ≤ N ≤ 30), and the pattern P. There can be a maximum of 35 test cases. The input terminates when N is 0.

Output

For each test case, print the case number and the answer, as shown below.

Sample Input Sample Output

4 0**1
5 *****
10 **01**01**
0

Case 1: 2
Case 2: 16
Case 3: 9