SP9936 CGW - Construct the Great Wall


The first line contains an integer **T** (1 ≤ T ≤ 50), indicating the number of test cases. Each test case contains several lines. The first line contains two integer **H**, **W** (1 ≤ **H**, **W** ≤ 8), indicating the number of rows and columns of the map. The following **H** lines contains **W** chars, indicating the map. 'o' represents a city, '.' represents a empty area and 'x' represents an enemy. You can assume that there will be at least one city on the map.

For each test case in the input, print one line: "Case #X: Y", where **X** is the test case number (starting with 1) and **Y** is the length of the shortest Great Wall (-1 if impossible).