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 was on, they calculate the total time the power was 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 x 8 grid. Each cell contains one of the following characters

1. . means land.
2. H means house.
3. G means power generator.
4. W means water.

Two adjacent cells can be connected by cables 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 are 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 could be sponsors who might use the pillars to advertise.

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 starts with an integer T (≤ 100), denoting the number of test 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 will be exactly one power generator and the total number of houses will be between 1 and 8 (inclusive).

For each test case, print the case number and the minimum total cost in thousands.