{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"It\u0027s a dark, cloudy and spooky night. The ghosts of \u0027VutPara\u0027 graveyard have awakened. They are planning to take revenge against humans. They are dead but the humans are alive that\u0027s their main headache. So, they want to frighten all the people nearby.\n\n\u0027Vutpara\u0027 can be described as an **n x n** grid. Each cell can be one of the following types:\n\n* `.` - The cell is empty.\n* `G` - The cell contains a ghost.\n* `H` - The cell contains a human\n* `#` - The cell contains over-polluted air, the ghosts can\u0027t fly over this cell.\n\nThe 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).\n\nThe 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."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 200)**, denoting the number of test cases.\n\nEach case starts with a blank line and an integer **n (5 \u0026#8804; n \u0026#8804; 25)**. Then **n** lines follow. Each of the line contains **n** characters each describing \u0027Vutpara\u0027. 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."}},{"title":"Output","value":{"format":"MD","content":"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\u0027s not possible to frighten all the people."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\n8\n....##..\n.....#..\n..#...G.\nG...####\nH#..HG.G\n#....#.#\nH.#G..H.\n..##...#\n\n6\n......\nG.....\n......\n......\n......\n.....H\n\n6\n.....G\n.H....\n......\n......\n....H.\nG.....\n\n6\n#.#G#.\nG....#\nG..##.\nH###.#\n...#H#\n..#GHH\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 12\nCase 2: 20\nCase 3: 12\nCase 4: Vuter Dol Kupokat\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}