Grid Infection with Immune Cells Until Stable

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

Extending the previous problem, the grid may also contain immune cells 'I':

'I' can never be infected.

'I' does not infect others (it is not counted as infected).

Each day (synchronously), any healthy '.' cell with at least T infected 'X' neighbors among its 8 neighbors becomes 'X'. 'I' always stays 'I'.

Return the number of days until the grid becomes stable (no new infections occur).

Example

Input

3 3

1

I..

.X.

...

Output

1

Complete solveGridInfectionWithImmuneCells. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.