Spinning Blade (Large)

You are building a trap for your hideout: a spinning blade. The blade is cut out of a heavy metal sheet that carries a painted grid of square cells, $R$ rows by $C$ columns. First you cut out a square of $K \times K$ cells aligned to the grid, where $K \ge 3$. Then you cut away the four $1 \times 1$ corner cells of that square. What is left is the blade.

Every cell was supposed to have mass $D$, but the sheet is not perfectly uniform, so the cell in row $i$ and column $j$ has mass $D + w_{ij}$. The shaft goes exactly through the center of the $K \times K$ square, so the blade spins properly only if its center of mass sits exactly at that center.

Given the grid and the mass of every cell, find the largest $K$ such that some $K \times K$ square inside the sheet gives a blade whose center of mass is exactly at the center of the square.

The first line contains the number of test cases $T$. Each test case starts with a line of three integers $R$, $C$ and $D$: the number of rows, the number of columns, and the mass you expected each cell to have. The next $R$ lines each contain $C$ digits with no spaces. The $j$-th digit of the $i$-th line is $w_{ij}$, the difference between the actual mass and the expected mass of that cell. Each cell has uniform density, and its mass is an integer between $D$ and $D + 9$, inclusive.

Limits

• $1 \le T \le 20$
• $3 \le R \le 500$
• $3 \le C \le 500$
• $1 \le D \le 10^6$
• $0 \le w_{ij} \le 9$
• The size of the input is at most 625KB.

For each test case, print one line of the form Case #x: K, where $x$ is the test case number starting from 1 and $K$ is the largest blade size you can cut out. If no blade of size 3 or more has its center of mass at the center of its square, print IMPOSSIBLE in place of $K$.

The center of mass of a flat object is the point $c$ with this property: adding up $(p - c)\,\mathrm{mass}(p)$ over all points $p$ of the object gives the zero vector. Here $p$, $c$ and the zero are two dimensional vectors. The definition still works when each grid cell is treated as a single point that carries all of its mass at the center of the cell.

For an example, take a $3 \times 3$ sheet with $D = 7$ whose digit rows are 123, 234 and 345 from top to bottom. The only candidate blade is the whole square with its four corner cells cut away. Put the origin at the bottom left corner of the sheet, let $x$ grow to the right and $y$ grow up, so every cell center lands on half integer coordinates. The five remaining cells have masses 9, 9, 10, 11 and 11, and their center of mass is $(1.54, 1.46)$:

$(-1.04, 0.04) \times 9 + (-0.04, 1.04) \times 9 + (-0.04, 0.04) \times 10 + (-0.04, -0.96) \times 11 + (0.96, 0.04) \times 11 = (0, 0)$

The center of the square is $(1.5, 1.5)$, so this blade is not balanced.