Problem E
Bangladesh Sequences
Input: Standard Input

Output: Standard Output

Bangladesh Sequences are sequences of at most 15 letters. The allowed letters in the sequence of length 15 are A, B, C, D, E, F, G, H, I, J, K, L, M, N and O. Similarly allowed letters in a sequence of length 4 are A, B, C, D; allowed letters in a sequence of length 5 are A, B, C, D, E and so on. The first 15 letters of English alphabet have the values 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78 and 79 respectively. A sequence of length n (n<16) formed with first n letters of English alphabet is called Bangladesh Sequence if it fulfills at least one of the following conditions (Multiple fulfillment is also not harmful):

a) If any two characters are equal. So ABAD is a Bangladesh sequence according to this rule only.

b) If the absolute value of the difference of position of any two characters is equal to the absolute value of the difference of their values. So ABCD is a Bangladesh sequence according to this rule. Position of A is 1 and position of B is 2, |2-1|=1 and |A-B|=|65-66|=1 as well.

c) If the value of any two adjacent characters differ by two.

d) If the value of any two characters who has one character between them differs by 1.

You will have to find the number of Bangladesh Sequences under some given constraints.

Input

The input file contains less than 502 sets of input. Each set starts with an integer n, which indicates that this set is speaking about a Bangladesh sequence of length n. The next n lines define the constraints of the n positions of the sequence. A question mark means that in the corresponding position any one of the first n characters of English alphabet is feasible. If the line contains one or more alphabet instead of ‘?’ then it means that those characters are allowed in the corresponding position. For example the second set in the sample input asks to find Bangladesh Sequence of length 4, whose first character can only be ‘A’ and ‘B’ although other positions can contain any one of the characters ‘A’, ‘B’, ‘C’ and ‘D’. Input is terminated by a set whose value of n is zero. This set should not be produced.

Output

For each set of input produce one line of output. This line should contain the output serial no as shown in the sample output and then it should contain how many Bangladesh sequences are there with the given constraints and length.

Sample Input Output for Sample Input

Case 1: 64

Case 2: 128

Problemsetter: Shahriar Manzoor