회전 칼날 (Small)

비밀 은신처에 놓을 함정이 지루해져서, 고전적이지만 언제나 재미있는 회전 칼날을 만들기로 했다. 칼날을 잘라 낼 아주 무거운 금속판을 주문했고, 판 위에는 가로 C칸, 세로 R칸짜리 정사각형 격자가 그려져 나온다. 칼날의 모양도 정해 두었다. 먼저 K × K칸으로 이루어진 큰 정사각형을 자른다. 여기서 K ≥ 3이다. 그다음 그 정사각형의 네 귀퉁이에서 1 × 1칸을 하나씩 잘라 내면 칼날이 완성된다. 여기까지 정하고 판이 도착하기를 기다렸다.

판이 도착하자 두께가 고르지 않다는 사실을 알게 됐다. 칸마다 질량이 정확히 D일 것으로 기대했지만 실제 질량은 조금씩 달랐다. 칼날 한가운데에 축을 꽂고 아주 빠르게 돌릴 생각이므로, 칼날의 질량중심도 칼날의 중심과 정확히 일치해야 한다. 평면 물체의 질량중심 정의는 노트에 있다.

격자와 각 칸의 질량이 주어질 때, 질량중심이 중심과 정확히 일치하도록 만들 수 있는 칼날의 최대 크기를 구하라.

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 R, C, D가 주어진다. R과 C는 격자의 세로와 가로 크기이고, D는 각 칸에 기대한 질량이다. 다음 R개의 줄에는 각각 C개의 숫자 wij가 공백 없이 주어진다. wij는 실제 질량과 기대 질량의 차다. 각 칸의 밀도는 균일하며, 질량은 D + 0 이상 D + 9 이하의 정수다.

제한

• 1 ≤ T ≤ 20
• 0 ≤ wij ≤ 9
• 입력 파일의 크기는 625KB를 넘지 않는다.
• 3 ≤ R ≤ 10
• 3 ≤ C ≤ 10
• 1 ≤ D ≤ 100

각 테스트 케이스마다 "Case #x: K" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, K는 잘라 낼 수 있는 칼날의 최대 크기다. 크기가 3 이상인 칼날을 하나도 만들 수 없으면 K 자리에 IMPOSSIBLE을 출력한다.

평면 물체의 질량중심은 다음 조건을 만족하는 점 $c$로 정의된다. 물체에 속한 모든 점 $p$에 대해 $(p - c) \times \mathrm{mass}(p)$를 모두 더하면 $0$이 되어야 한다. 여기서 $p$, $c$, $0$은 모두 2차원 벡터다. 격자의 각 칸을 그 칸의 중심에 질량이 전부 모인 하나의 점으로 보면 이 정의를 그대로 쓸 수 있다.

실제로 평평한 물체의 질량중심 아래에 손가락을 대면 물체가 떨어지지 않고 균형을 잡는다.

판의 왼쪽 아래 귀퉁이를 $(0, 0)$으로 두고 오른쪽과 위쪽으로 좌표가 커진다고 하자. 예제의 두 번째 테스트 케이스에서 만들 수 있는 칼날은 네 귀퉁이를 잘라 낸 3 × 3 칼날 하나뿐이고, 이 칼날의 질량중심은 $(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)$이 성립하므로 확인할 수 있다. 이 점은 칼날의 중심인 $(1.5, 1.5)$와 다르므로 답은 IMPOSSIBLE이다.