Drop Zone | cho.sh

Problem

Special teams run evacuation missions and supply gathering missions on a regular schedule. The first job on such a mission is to put up a perimeter of barricades. Barricades are expensive and slow to install, so the team wants to seal off an area with as few of them as possible.

You are given several maps of high-interest drop zones. Write a program that reports, for each map, the minimum number of barricades needed to seal off the drop zone.

Zombies approach from outside the map, so every open area on the border is reachable by them. A barricade may be placed between any two adjacent open areas, and the drop zone counts as an open area. Every zone outside the map is an open area too.

A cell on the border touches an outside zone on each of its sides that faces off the map. Sealing such a cell off from the outside therefore costs one barricade per side, and two for a cell in a corner of the map.

Symbol	Description
`X`	Impassable. Zombies cannot move through these areas.
`.`	Open area. Zombies move up, down, left and right, never diagonally. Barricades may be placed between open areas.
`D`	Drop zone. This zone must be protected at all costs, so barricades have to block every route from the edges of the map into it. For zombie movement and barricade placement it behaves exactly like an open area. Every map has exactly one drop zone and its cells are connected. The drop zone may sit on the edge of the map.

Input

The first line contains the number of maps $N$ ( $1 \le N \le 20$ ).

Each map begins with a line holding the number of rows $R$ and the number of columns $C$ ( $1 \le R, C \le 150$ ), followed by the map on $R$ lines. Every line is exactly $C$ characters long.

Output

For each map, print on its own line the minimum number of barricades needed to seal off the drop zone.