Count Diamonds on the Table

The table is represented by an n × m grid. A diamond is defined as a shape whose overall outline is a rhombus (a square rotated by \(45^\circ\)) with its border cells all being # and its internal cells (if any) all being .. Formally, a diamond of order \(k\) (with \(k \ge 1\)) has a height of \(2k+1\) rows. If its top cell is located at \((i,j)\) then for each row \(d\) (where \(0 \le d \le 2k\)) let \(t = |d-k|\). In that row, the segment from column \(j-(k-t)\) to \(j+(k-t)\) (inclusive) describes the diamond. The cells at the two ends of this segment must be # and all cells in between must be ..

Given an n × m grid representing the table, count how many diamonds are placed on the table. It is guaranteed that each diamond drawn will exactly follow the pattern described, and diamonds do not overlap.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns). The following \(n\) lines each contain a string of length \(m\) consisting only of the characters # and ., representing the table.

outputFormat

Output a single integer representing the number of diamonds on the table.

sample

3 3
.#.
#.#
.#.

1