I. Foggy Butterflies
time limit per test
0.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Watson is on a foggy mountain represented by an $$$n \times m$$$ grid.

Each cell contains one of:

  • . (empty),
  • * (a butterfly),
  • # (a rock, impassable).

Watson can move in 4 directions (up, down, left, right) to a neighboring cell in one step. He cannot step on rocks.

Because of fog, Watson can only plan to catch the next butterfly if it is reachable within at most $$$k$$$ steps from his current position, where $$$1 \le k \le 10$$$.

Watson catches a butterfly when he visits its cell. He may choose the first butterfly to catch freely. After catching one butterfly, he may move to another butterfly only if the shortest path length between their cells (avoiding rocks) is at most $$$k$$$. Watson cannot catch the same butterfly twice.

Your task is to compute the maximum number of butterflies Watson can catch.

Input

The first line contains three integers $$$n$$$, $$$m$$$, $$$k$$$: $$$ 1 \le n,m \le 2000,\quad 1 \le k \le 10. $$$ The next $$$n$$$ lines each contain a string of length $$$m$$$ consisting of ., *, #.

It is guaranteed that the number of butterflies in the grid does not exceed $$$20$$$.

Output

Print one integer: the maximum number of butterflies Watson can catch.

Examples
Input
2 2 1
*#
.*
Output
1
Input
1 1 8
.
Output
0
Input
21 17 5
#.....###....#.#.
.#*##............
.#..##.......#.##
...#.#.....*.###.
..#..**.#..*.....
###.....##....*.#
#..**#..........*
...#.#.......*...
..#....*.......#.
....#...#........
#.#...#..#*......
..#...##..#.#....
.*....#.#..##..##
.....#....#*#....
#...........*#...
.##.*..#.......##
#...*..*#..##..#.
.#....#..#.#....#
#.#......#.....##
.*..*...#.#.#...#
#....###.##......
Output
6
Input
7 9 4
.*#..#...
..*.*..*.
.**..**..
*...#...#
*.*.*..*.
.*.*..*..
**.#..*..
Output
19
Input
11 24 3
..*..*#.##..*....#....*.
.#.#..#..#.#....#..#..##
......#...*##.#.........
..#....###.#...###.##...
.#....#...#........##...
....#...#...#.#.###.#..#
#.*.#..#...#..##.#..#...
##..##...*...##.#..#.##.
..##..#.#*......#...#...
###..#.#........##..*...
....##.#*###...#........
Output
3