Problem A
Boom!

Photo by whatleydude on flickr.

Blowing things up usually requires careful planning, something Luntas is not especially good at. He has randomly thrown a number of bombs on his backyard, which can be seen as a grid of width and height $N$. Now he only has one bomb left, which he intends to use to start the explosion and the resulting chain reactions.

A bomb explodes in a cross along the axes of the grid, with a blast radius of $R$. If a bomb comes in the way of an explosion, that bomb will explode as well. Explosions can not pass through the many rocks in Luntas backyard though. If an explosion reaches a tree stump, it will blow the stump up and continue through the stump. A blast radius of $R$ means that the blast will affect all the squares with distance at most $R$, which have either the same $x$-coordinate or the same $y$-coordinate as the bomb itself.

Figure 1: Illustration of the first sample and bomb patterns. The circled bomb is one of the possible solutions. The square (2, 4) will not blow up the stumps despite having line of sight to both stumps; the distance to the stump at (2, 0) is greater than the blast radius.

He now needs your help to find out at how many locations he can place his last bomb, such that if it explodes, all the stumps on the field will blow up. He may only place the last bomb on an empty square.

Input

The first line consists of two integers: the backyard size $1 \le N \le 1\, 000$ and the blast radius $1 \le R \le 20$. Then follow $N$ lines with $N$ characters each, describing the backyard as an $N \times N$ grid. Each character is one of:

. – an empty square.

# – an obstacle.

* – a bomb.

S – a tree stump.

Output

Output should consist of a single integer; the number of locations Luntas can place the last bomb on to blow all the stumps up.

5 3
.*S#.
.....
....#
.*...
.S...

7

5 2
..S..
..#..
S#.#S
..#..
..S..

0