C. Clever Cell Choices
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Two players play the following game on an $$$N \times M$$$ grid:

  • Initially, each cell of the grid is either empty or occupied.
  • Players take turns placing a stone on an empty cell, occupying the cell. Each new stone must be adjacent to the last placed stone, with the exception of the starting stone that can be placed on any empty cell. A stone is adjacent to another stone if they are located in two cells that share a side.
  • The game ends whenever a player cannot place a stone according to the above rules. In that case, the player who cannot place a stone loses the game, and the other player wins.

A winning starting cell is a cell such that the first player wins the game if they place their starting stone there, assuming both players play optimally. Given a description of the initial grid, you must tell how many winning starting cells it has.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 50$$$) indicating the dimensions of the grid.

Each of the next $$$N$$$ lines contains a string of length $$$M$$$. In the $$$i$$$-th string, the $$$j$$$-th character describes the initial state of cell $$$(i,j)$$$. The character is either "." (dot) denoting an empty cell, or "#" (hash) representing an occupied cell.

Output

Output a single line with an integer indicating the number of winning starting cells.

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