CF1106A.Lunar New Year and Cross Counting

传统题 时间 2000 ms 内存 256 MiB 3 尝试 1 已通过 1 标签

Lunar New Year and Cross Counting

Lunar New Year is approaching, and you bought a matrix with lots of "crosses".

This matrix MM of size n×nn \times n contains only 'X' and '.' (without quotes). The element in the ii-th row and the jj-th column (i,j)(i, j) is defined as M(i,j)M(i, j), where 1i,jn1 \leq i, j \leq n. We define a cross appearing in the ii-th row and the jj-th column (1<i,j<n1 \lt i, j \lt n) if and only if $M(i, j) = M(i - 1, j - 1) = M(i - 1, j + 1) = M(i + 1, j - 1) = M(i + 1, j + 1) =$ 'X'.

The following figure illustrates a cross appearing at position (2,2)(2, 2) in a 3×33 \times 3 matrix.

  
X.X  
.X.  
X.X  

Your task is to find out the number of crosses in the given matrix MM. Two crosses are different if and only if they appear in different rows or columns.

Input

The first line contains only one positive integer nn (1n5001 \leq n \leq 500), denoting the size of the matrix MM.

The following nn lines illustrate the matrix MM. Each line contains exactly nn characters, each of them is 'X' or '.'. The jj-th element in the ii-th line represents M(i,j)M(i, j), where 1i,jn1 \leq i, j \leq n.

Output

Output a single line containing only one integer number kk — the number of crosses in the given matrix MM.

Note

In the first sample, a cross appears at (3,3)(3, 3), so the answer is 11.

In the second sample, no crosses appear since n<3n \lt 3, so the answer is 00.

In the third sample, crosses appear at (3,2)(3, 2), (3,4)(3, 4), (4,3)(4, 3), (4,5)(4, 5), so the answer is 44.

Samples

5
.....
.XXX.
.XXX.
.XXX.
.....
1
2
XX
XX
0
6
......
X.X.X.
.X.X.X
X.X.X.
.X.X.X
......
4

在线编程 IDE

建议全屏模式获得最佳体验