beecrowd | 1432
# Triple-Free Binary Strings

**Timelimit: 3**

By Rujia Liu, TU China

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?

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.

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

Sample Input | Sample Output |

4 0**1 |
Case 1: 2 |