Grid Infection Spread 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

Grid Infection Spread Until Stable (8-direction, threshold)

You are given an m×n grid grid where each cell is either infected 'X' or healthy '.'.

Each day, perform a synchronous update: for every healthy cell '.', count the number of infected 'X' cells among its 8 neighbors (4-directional + 4 diagonals). If the count is ≥ T, that cell becomes infected 'X' at the end of the day. Infected cells never recover or disappear.

Return the number of days until the grid becomes stable (i.e., after some day’s update, no new infections occur).

Notes:

Updates are synchronous: changes on day d depend only on the state at the start of day d.

You may assume 1 ≤ m,n ≤ 200 and 0 ≤ T ≤ 8.

Examples:

grid=["...", ".X.", "..."], T=1 → 1

same grid, T=2 → 0

Example

Input

3 3

1

...

.X.

...

Output

1

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