### Problem Statement

You are given String[] photo, representing a satellite photo of a military base. Photo contains two types of characters - '.' characters represent an empty area, and '*' characters represent parts of buildings. Two non-empty squares A and B on photo belong to the same building if and only if there exist a chain of squares where the first square is A, the last square is B, and each pair of consecutive squares in the chain shares a common side or angle.

There are some school buildings on the photo. The distinguishing feature of the school buildings is the shape. Each such building is a rectangular frame (in other words, it is the result of subtracting non-empty solid rectangle A from solid rectange B, and rectangle A lies completely inside B without touching by borders). Each side of the frame must be k cells thick and must be parallel to an edge of the photo (see examples for clarification). Note that a school building can't contain any other buidings inside its internal part (see example 2 for clarification).

Return the number of school buildings on the photo.

### Definition

 Class: MilitaryBase Method: getSchoolBuildingCount Parameters: String[], int Returns: int Method signature: int getSchoolBuildingCount(String[] photo, int k) (be sure your method is public)

### Constraints

-photo will contain between 1 and 50 elements, inclusive.
-Each element of photo will contain between 1 and 50 characters, inclusive.
-Each element of photo will contain the same number of characters.
-k will be between 1 and 24, inclusive.
-Each element of photo will contain only '.' or '*' characters.

### Examples

0)

 ```{"***......", "*.*......", "***.*****", "....*****", "....**.**", "....**.**", "....**.**", "....*****", "....*****"}``` `1`
`Returns: 1`
 The topleft building at the photo is a school. The other one looks similar to a school, but its sides are too thick.
1)

 ```{"*****.*****", "*****.*****", "**.**.**.**", "*****.*****", "*****.*****", "...........", "*****.*****", "**.**.*****", "*****.**.**", "...........", "****.......", "****.......", "**.........", "**........."}``` `2`
`Returns: 2`
 Two top buildings are schools. The left building in the middle row is a rectangle frame, but its top and bottom sides are of incorrect thickness. The two remaining buildings are not rectangle frames at all.
2)

 ```{"*********", "*.......*", "*.*****.*", "*.*...*.*", "*.*...*.*", "*.*****.*", "*.......*", "*********"}``` `1`
`Returns: 1`
 Only the inner building is a school.
3)

 ```{"..........", ".****.....", ".*..*.....", ".****.....", ".....****.", ".....*..*.", ".....****.", ".........."}``` `1`
`Returns: 0`
 Here we have only one building and it's not a school (remember that two squares sharing a commong angle belong to the same building).
4)

 ```{"*********.", "*.......*.", "*.***...*.", "*.*.*.*.*.", "*.***...*.", "*.......*.", "*********.", "*********."}``` `1`
`Returns: 1`
 This photo contains one school building and two buildings which are not a school.
5)

 ```{"*******", "*.....*", "*.**..*", "*..**.*", "*.....*", "*******"}``` `1`
`Returns: 0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8814

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12228&pm=8814

Mike Mirzayanov

#### Testers:

PabloGilberto , SnapDragon , Olexiy , ivan_metelsky

Search