Grid Infection with Immune Cells Until Stable

At the end of each day, a healthy cell . becomes X if it had at least T infected neighbors X at the start of that day. Neighbors include up, down, left, right, and the four diagonals, 8 directions in total. Infected cells never recover. Return the last day on which a new infection occurs; if the grid is already stable initially, return 0. A check day with no change is not counted. An immune cell I is never infected and does not count toward infected neighbors.

输入格式

The first line contains n m, the second line contains T, followed by n lines of m consecutive characters. 1≤n,m≤200, 0≤T≤8. Each character is X, ., or I. Problem 8 uses the full scale given in Problem 7.

输出格式

A single non-negative integer, the number of rounds in which new infections occur.

样例 1

输入：

3 3
1
I..
.X.
...

输出：

1

样例 2

输入：

3 3
2
...
.X.
...

输出：

0

样例 3

输入：

1 4
0
....

输出：

1

样例说明

In Example 1 the center infection spreads to all non-immune neighboring cells at once, so the answer is 1. In Example 2 there is only 1 infected neighbor while the threshold is 2, so the answer is 0. In Example 3 the threshold is 0, so no infection source is needed, and every healthy cell is infected on day 1.