COMP4128 Oil Skimming
A. Oil Skimming
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a map of the oil slick represented as a $$$N\times N$$$ grid. Each cell on the grid corresponds to a $$$10$$$ meter by $$$10$$$ meter square marked either as oil or water.

Large slicks of crude oil are scooped up by enterprising oil barons. One such oil baron has a special plane that can skim the surface of the water collecting oil on the water's surface. The plane collects oil in rectangular scoops, each measuring $$$10$$$ meters by $$$20$$$ meters. These scoops can be oriented either east-west or north-south. A scoop must be completely covered in oil for it to be profitable.

Calculate the maximum number of profitable scoops that can be extracted from this map.

Input

The first line of input consists of a single integer $$$N$$$ ($$$1\leq N\leq 300$$$), the size of the square grid.

The following $$$N$$$ lines each contain $$$N$$$ characters that represent the cells of a row in a grid. A character of '#' represents an oily cell and a character of '.' represents a pure water cell.

Output

Output a single integer, the maximum number of profitable scoops that can be extracted.

Examples
Input
1
#
Output
0
Input
4
..##
..##
##..
##..
Output
4
Input
6
......
.##...
.##...
....#.
....##
......
Output
3