You have recently gained a large piece of free real estate!
The real estate may be represented as a grid of size M × N. These grid squares may consist of flat open ground, ponds or forests.
You wish to build some houses on flat open ground. Due to the principles of Feng Shui, these houses must be at most K minutes walk away from a pond. You can walk from a grid square to any grid square that shares an edge in 1 minute, but you cannot walk through ponds or forests.
How many grid squares are suitable for building your houses?
The first line of input contains three integers, M, N and K.
The next M lines of input contain strings of N characters, indicating the contents of the grid.
'.' represents flat ground, '#' represents forest and '*' represents a pond.
The first and only line of output should contain a single integer, denoting the number of grid squares that you can build houses on.
For all subtasks, 1 ≤ M, N, M × N ≤ 1000000 and 1 ≤ K ≤ 109.
Subtask 1 (65%): There is at most one pond.
Subtask 2 (15%): There are no forests.
Subtask 3 (20%): There are no more constraints.
Subtask 4 (0%): Sample test cases.
Sample Input 1
3 3 3
Sample Output 1
Sample Input 2
5 5 8
Sample Output 2