DWITE, February 2013, Problem 4

In a typical "build a fence" scenario, farmer John needs to fence his animals in the cheapest way possible. In this case, "the cheapest" is defined as keeping them in the smallest area possible (well, somebody is buying those non-free-range products…). You observe that while it's simple to just box every marked location at the perimeter, some of the fencing is redundant. If a single fence has animals on two sides of it, it is redundant.

Consider the following configuration, where . represents empty space, # represents an animal, and F represents a fence:

........    FFFFFFFF
.#.#..#. => F#.#FF#F
........    FFFFFFFF

Wanting to enclose # locations, the only empty space remaining is the omitted fence between the left two #s. The rightmost # is completely enclosed (you can imagine that FF leaves enough space to have a pathway in between).

If a . cell is adjacent to at least ~2~ # cells out of its ~4~ direct neighbours, then it will be a . cell. If a . cell is adjacent to at least ~1~ # cell out of its ~8~ neighbours (including diagonals), then it will be an F cell. In any other case, the cell will remain a ..

Your goal is to determine the number of F cells for a given input grid.

Note that some fences may have to be placed outside of the input grid. You should treat all cells outside of the input grid as . cells.

Input Specification

The input will contain 5 test cases (the sample input will contain only 1).

Each case will start with a line containing a single integer, ~1 \le N \le 15~, representing the length of the side of John's square farm.

The following ~N~ lines contain strings of length ~N~, describing the farm's layout. Each string will contain only . and # characters.

Output Specification

For each input grid, output the number of fence cells required.

Sample Input

5
#.#..
.##..
.....
.#..#
...#.

Sample Output

24

Explanation for Sample

Fences should be placed as follows:

FFFFF..
F#.#F..
F.##F..
.F.FFFF
.F#F.#F
.FFF#.F
...FFF.

Problem Resource: DWITE