회전 칼날

비밀 은신처 설계에 함정을 넣는 데 싫증이 난 당신은 고전적이지만 언제나 즐거운 장치인 회전 칼날을 선택하기로 했다. 당신은 칼날을 잘라 낼 매우 무거운 금속판을 주문했으며, 금속판에는 균일한 정사각형 $C \times R$ 격자가 그려질 것이다. 당신은 칼날에 가장 적합한 모양을 정했다. 먼저 $K \times K$개의 격자 칸으로 이루어진 큰 정사각형을 자른다. 여기서 K ≥ 3이다. 그런 다음 정사각형의 네 모서리에 있는 1×1 칸을 잘라 내어 칼날을 완성한다. 이 모든 것을 정한 뒤, 당신은 금속판이 도착하기를 기다리기 시작했다.

금속판이 도착했을 때, 당신은 금속판에 결함이 있다는 사실을 알고 충격을 받았다! 각 칸의 질량이 D일 것으로 예상했지만, 두께 차이 때문에 질량이 조금씩 달라질 수 있었다. 당신은 칼날의 정확한 중심에 축을 삽입하여 매우 빠르게 회전시키려 하므로, 이는 좋지 않다. 따라서 칼날의 질량 중심 역시 정확히 그 중심에 있어야 한다. 평평한 물체의 질량 중심에 대한 정의는 아래에서 확인할 수 있다.

격자와 각 칸의 질량이 주어질 때, 질량 중심이 정확히 그 중심에 있도록 만들 수 있는 칼날의 가능한 최대 크기는 얼마인가?

제한

1 ≤ T ≤ 20. 0 ≤ $w_{ij}$ ≤ 9. 입력 파일의 크기는 625KB를 초과하지 않는다. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

3 ≤ R ≤ 10. 3 ≤ C ≤ 10. 1 ≤ D ≤ 100. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ R ≤ 500. 3 ≤ C ≤ 500. 1 ≤ D ≤ $10^{6}$. 시간 제한: 60초.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 3개의 정수 R, C, D가 있는 줄로 시작하며, 이들은 각각 격자의 크기와 각 칸에 있을 것으로 예상한 질량을 나타낸다. 이어지는 R개의 줄에는 각각 C개의 숫자 $w_{ij}$이 주어지며, 각 숫자는 해당 격자 칸의 실제 질량과 예상 질량의 차이를 나타낸다. 각 칸의 밀도는 균일하지만, 질량은 D + 0 이상 D + 9 이하의 정수일 수 있다.

각 테스트 케이스마다 "Case #x: K"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, K는 잘라 낼 수 있는 칼날의 가능한 최대 크기이다. 크기가 적어도 3인 적합한 칼날을 찾을 수 없다면, 대신 "IMPOSSIBLE"를 출력한다.

2D 물체의 질량 중심은 형식적으로 점 c로 정의된다. 물체의 모든 점 p에 대해 (p - c) * mass(p)의 합을 계산하면 그 결과는 반드시 0이어야 한다. 여기서 p, c, 0는 이차원 벡터이다. 각 격자 칸의 모든 질량이 그 중심에 모여 있는 "point"으로 취급해도 이 정의가 성립한다.

실제로는 평평한 물체의 질량 중심 아래에 손가락을 놓고 그 물체를 손가락 위에서 균형 잡을 수 있다. 물체는 떨어지지 않을 것이다.

예를 들어 설명하면, 두 번째 예제 테스트 케이스에서 잘라 낼 수 있는 유일한 칼날인 모서리를 잘라 만든 3x3 칼날의 질량 중심은 점 (1.54, 1.46)에 있다. 이때 금속판의 왼쪽 아래 모서리 좌표는 (0, 0)이고, 좌표는 각각 오른쪽과 위쪽으로 증가한다고 가정한다. 이는 다음 등식이 성립하는지 확인하여 검증할 수 있다: (-1.04, 0.04) * 9 + (-0.04, 1.04) * 9 + (-0.04, 0.04) * 10 + (-0.04, -0.96) * 11 + (0.96, 0.04) * 11 = (0, 0).