Spinning Blade (Small)

The traps in your secret hideout have become boring, so you decided on something classical and always enjoyable: the spinning blade. You ordered a really heavy metal sheet to cut the blade out of, and a uniform square grid of C columns by R rows will be painted on it. You have already settled on the shape. First you cut a large square made of K × K grid cells, where K ≥ 3. Then you cut the four 1 × 1 corner cells out of that square, and what is left is the blade. With all that decided, you waited for the sheet to arrive.

When the sheet arrived, you found that it had imperfections. You expected every cell to have mass D, but the mass varies a little because the thickness varies. That is a problem, because you want to insert a shaft exactly in the center of the blade and spin it very fast, so the center of mass of the blade has to be exactly at its center too. The definition of the center of mass of a flat body is in the note below.

Given the grid and the mass of each cell, find the largest blade you can make whose center of mass is exactly at its center.

The first line of the input gives the number of test cases, T. T test cases follow. Each one starts with a line containing three integers R, C and D. R and C are the dimensions of the grid, and D is the mass you expected each cell to have. The next R lines each contain C digits wij with no spaces, giving the difference between the actual and the expected mass of that grid cell. Each cell has a uniform density, and its mass is an integer between D + 0 and D + 9, inclusive.

Limits

• 1 ≤ T ≤ 20
• 0 ≤ wij ≤ 9
• The size of the input file will not exceed 625KB.
• 3 ≤ R ≤ 10
• 3 ≤ C ≤ 10
• 1 ≤ D ≤ 100

For each test case, output one line containing "Case #x: K", where x is the test case number starting from 1 and K is the largest possible size of the blade you can cut out. If no acceptable blade of size at least 3 exists, print IMPOSSIBLE in place of K.

The center of mass of a 2D object is formally defined as a point $c$. If you compute the sum of $(p - c) \times \mathrm{mass}(p)$ over all points $p$ in the object, you must get $0$. Here $p$, $c$ and $0$ are two-dimensional vectors. The definition also works if you treat each grid cell as a single point that holds all of its mass at the cell's center.

In real life, you could place your finger under a flat object's center of mass and balance the object on your finger. It would not fall.

Assume the bottom left corner of the sheet has coordinates $(0, 0)$, and the coordinates grow right and up. In the second test case of the example, the only blade that can be cut out is the 3 × 3 blade created by cutting away the corners, and its center of mass is at $(1.54, 1.46)$. You can verify this with the equality $(-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)$. That point differs from the center of the blade, which is $(1.5, 1.5)$, so the answer is IMPOSSIBLE.