Finally, you found the city of Gold. As you are fond of gold, you start collecting it. But there is so much gold that you are getting tired.

So, you want to find the minimum effort to collect all the gold.

You can describe the city as a 2D grid, where your initial position is marked by an x. An empty place will be denoted by a .. And the cells which contain gold will be denoted by g. In each move, you can go to all 8 adjacent cells inside the city.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case will start with a blank line and two integers, m and n (0 < m, n < 20) denoting the row and columns of the city respectively. Each of the next m lines will contain n characters describing the city. There will be exactly one x in the city and at most 15 gold positions.

For each case of input you have to print the case number and the minimum steps you have to take to collect all the gold and go back to x.