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-freerange 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 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.