It's a dark, cloudy and spooky night. The ghosts of 'VutPara' graveyard have awakened. They are planning to take revenge against humans. They are dead but the humans are alive that's their main headache. So, they want to frighten all the people nearby.

'Vutpara' can be described as an n x n grid. Each cell can be one of the following types:

• . - The cell is empty.
• G - The cell contains a ghost.
• H - The cell contains a human
• # - The cell contains over-polluted air, the ghosts can't fly over this cell.

The ghosts can move vertically or horizontally but not diagonally. And they can fly to any cell if the air is not over-polluted. It takes one minute to move to an adjacent cell. And it takes two minutes to frighten a human if the ghost is flying over the human (means that the position of the ghost and the human is same). But the ghosts are quite lazy, so any ghost can frighten at most one human. And after their work is done they want to go back to their grave (Initial position).

The night is getting over and they have a little time left. As they are smart enough they know all the human positions and the map. Now they want to frighten all the humans in the map using minimum time.

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

Each case starts with a blank line and an integer n (5 ≤ n ≤ 25). Then n lines follow. Each of the line contains n characters each describing 'Vutpara'. You can assume that number of ghosts is always greater than or equal to the number of humans and the number of ghosts is no more than 50. And there is at least one human in the map.

For each case of input, print the case number and the minimum time needed to frighten all the people or Vuter Dol Kupokat if it's not possible to frighten all the people.