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. To be specific, if two perimeter **non-corner** segments overlap, than that space doesn't require a fence. E.g.

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

Wanting to enclose # locations, the only empty space remaining is the omitted fence. The rightmost # is completely enclosed (you can imagine that FF leaves enough space to have a pathway in between). Make sure to think through all the various configurations that might need to be fenced.

The input file **DATA4.txt** will contain 5 test cases. Each case will start with a line containing a single number 1 <= **N** <= 15 representing the length of the side of John's square farm, followed by *N* lines describing the layout of the animals.

- . — empty location
- # — an animal

The output file **OUT4.txt** will contain 5 lines of output. Each denotes the amount of fencing required to completely enclose all animals as described above.

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

25

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