The city ‘AjobakahD’ has a lot of problems with electricity. Load shedding is a common problem here and people are quite used to it. Instead of calculating the total time the power is on, they calculate the total time the power is off. And of course the later one is always greater. There is a small area in the city, which has not yet been enlightened with any load shedding! That means they haven’t got the electricity connection yet. Now the Power Development Board (PDB) wants to set electricity connection in that area. Since the overall power in that city is not sufficient, they have decided to build a power generator in that area and want to connect all the houses to the generator. The area can be modeled as an 8 × 8 grid. Each cell contains one of the following characters • ‘.’ means land • ‘H’ means house • ‘G’ means power generator • ‘W’ means water Two adjacent cells can be connected by ca- bles and the cost is 1 thousand. Two cells are said to be adjacent if they share a side. But two adjacent cells can only be connected if none of the cells is empty. Empty means either land or water. In such case, pillars can be built in the cells and after that they can be connected. The cost of placing a pillar in a land and water cell is pl and pw thousand respectively. Remember that both the costs can be zero, because there can be sponsors who might use the pillars to advertise themselves. Now given the modeled grid of the area, the PDB wants to find the minimum cost to connect all the houses to the power generator directly or indirectly. That’s why they seek your help, as you are one of the finest programmers in town. Input Input starts with a positive integer T (T ≤ 200) denoting the number of cases. Each case starts with two integers pl and pw (0 ≤ pl,pw ≤ 10). Then there will be 8 lines, each containing 8 characters from the set {., H, G, W}. You may assume that in any modeled grid, there is exactly one power generator and the total number of houses is between 1 and 8 (inclusive). Output For each test case, print the case number and the total cost in thousands. Look at the output for sample input for formatting details. Sample Input 2 0 10 H.W.WH..
2/2 ..W.W... ..WGW... ........ ........ ........ ........ ........ 00 H.W.WH.. ..W.W... ..WGW... ........ ........ ........ ........ ........ Sample Output Case 1: 12 Case 2: 7