회전 칼날 (큰 입력)

비밀 기지에 놓을 함정으로 회전 칼날을 만들기로 했다. 칼날은 무거운 금속판을 잘라서 만든다. 금속판에는 정사각형 칸이 $R$행 $C$열로 놓인 격자가 그려져 있다. 먼저 격자에 맞춰 $K \times K$ 칸짜리 정사각형을 잘라 낸다($K \ge 3$). 그다음 그 정사각형의 네 모서리에 있는 $1 \times 1$ 칸을 잘라 버린다. 남은 모양이 칼날이다.

칸 하나의 질량이 $D$일 것으로 예상했지만 판의 두께가 고르지 않아서, $i$행 $j$열 칸의 질량은 $D + w_{ij}$다. 축은 $K \times K$ 정사각형의 중심을 정확히 지나므로, 칼날의 질량 중심이 그 중심과 정확히 일치해야만 칼날이 제대로 돈다.

격자와 각 칸의 질량이 주어질 때, 질량 중심이 정사각형의 중심과 정확히 일치하는 칼날을 만들 수 있는 가장 큰 $K$를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $R$, $C$, $D$가 주어진다. 차례로 격자의 행 개수, 열 개수, 칸 하나에 예상한 질량이다. 다음 $R$개 줄에는 각각 숫자 $C$개가 공백 없이 주어진다. $i$번째 줄의 $j$번째 숫자가 $w_{ij}$이고, 그 칸의 실제 질량과 예상 질량의 차이다. 각 칸의 밀도는 균일하며 질량은 $D$ 이상 $D + 9$ 이하의 정수다.

제한

• $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$
• 입력의 크기는 625KB를 넘지 않는다.

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

평면 물체의 질량 중심은 다음 성질을 만족하는 점 $c$다. 물체의 모든 점 $p$에 대해 $(p - c)\,\mathrm{mass}(p)$를 더하면 영벡터가 된다. 여기서 $p$와 $c$, 영벡터는 모두 2차원 벡터다. 격자의 각 칸을 질량이 전부 칸 중심에 모여 있는 점 하나로 봐도 이 정의가 그대로 성립한다.

예를 들어 $D = 7$이고 숫자 줄이 위에서부터 123, 234, 345인 $3 \times 3$ 금속판을 보자. 만들 수 있는 칼날은 정사각형 전체에서 네 모서리 칸을 잘라 낸 모양 하나뿐이다. 금속판의 왼쪽 아래 꼭짓점을 원점으로 두고 $x$는 오른쪽, $y$는 위쪽으로 커진다고 하면 각 칸의 중심 좌표는 반정수가 된다. 남은 다섯 칸의 질량은 9, 9, 10, 11, 11이고 질량 중심은 $(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)$이므로 이 칼날은 균형이 맞지 않는다.