There is a grid map with $R$ rows and $C$ columns, where each country is a 4-connected region. Your task is to color the map using four colors: red, green, blue, and yellow, such that no two adjacent countries have the same color.

Coloring alone is boring, so you want to invite your girlfriend to help—you will color with red and green, and she will color with blue and yellow. Of course, a gentleman would not let his girlfriend get overworked, so she only needs to color at most 5 countries (exactly 5 is also fine).

Your task is to count the number of ways to color the map. Note that each of the four colors must be used at least once.

Input

The input contains no more than 100 test cases. The first line of each test case contains two integers $R$ and $C$ ($1 \le R, C \le 20$), representing the number of rows and columns of the grid. The following $R$ lines each contain $C$ uppercase letters. A 4-connected region of identical letters represents a country. It is guaranteed that the number of countries does not exceed 30, and for most test cases, the number of countries is relatively small.

Output

For each test case, output the test case number and the number of coloring schemes.

Examples

Input 1

2 4
AABB
BBAA
1 5
ABABA
4 7
AABAABB
ABBCCCB
BBAACBB
CCABBAC

Output 1

Case 1: 24
Case 2: 144
Case 3: 3776