Drop Zone

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.

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.

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