Refreshment Area

Interview

Time limit2sMemory limit512 MB

Summary

Count the number of D-long horizontal or vertical runs of empty cells in an N by M grid.

Level: Easy2 of 10
Topics: Array, Implementation, Brute force, String
Solved: No attempts yet

Problem

An international programming contest will be held in Japan, and the venue is being set up now. The venue is divided into a grid of $N$ cells in the north-south direction and $M$ cells in the east-west direction. Some cells hold contest equipment.

The organizers will set up one refreshment area inside the venue with snacks and drinks, so that contestants can take breaks during the contest. The refreshment area must be $D$ consecutive cells in the north-south direction or in the east-west direction. However, the refreshment area cannot be placed on a cell that holds equipment.

Write a program that computes the number of ways to place the refreshment area in the venue.

Input

The input consists of $1 + N$ lines.

The first line contains three integers $N$ , $M$ , $D$ ( $1 \le N \le 100$ , $1 \le M \le 100$ , $2 \le D \le 100$ ) separated by spaces. The venue is a grid of $N$ cells north to south and $M$ cells east to west, and the refreshment area is $D$ consecutive cells in the north-south or east-west direction.

Each of the next $N$ lines contains a string of $M$ characters describing the venue. The $j$ -th character of the $i$ -th of these lines ( $1 \le i \le N$ , $1 \le j \le M$ ) is either # or . and gives the state of the cell in the $i$ -th row from the north and the $j$ -th column from the west. # means the cell holds equipment, and . means it does not.

Output

Print the number of ways to place the refreshment area in the venue on one line.

Hint

In the first sample, there are 12 ways in total to place the refreshment area, as shown in the figure below.

Examples2

Example 1
Input
```
3 5 2
...#.
#...#
....#
```
Expected output
```
12
```

Example 2

Input

4 7 5
.#.....
.....##
.......
#......

Expected output