회로 기판

Arsh는 최근 재활용하고 싶은 오래된 직사각형 회로 기판을 발견했다. 회로 기판은 R개의 행과 C개의 열로 이루어진 정사각형 칸들로 구성된다.

회로 기판의 각 칸에는 밀리미터 단위로 측정되는 두께가 있다. r번째 행과 c번째 열에 있는 칸의 두께는 $V_{r,c}$이다. 각 행에서 가장 두꺼운 칸과 가장 얇은 칸의 두께 차이가 K보다 크지 않으면 회로 기판은 좋은 회로 기판이다.

원래 회로 기판은 좋은 회로 기판이 아닐 수도 있으므로, Arsh는 좋은 부분 회로 기판을 찾으려고 한다. 원래 기판에서 축에 평행한 부분 직사각형을 선택하고 그 부분 직사각형 안의 칸들을 취하면 부분 회로 기판을 얻을 수 있다. Arsh가 원래 기판에서 가장 큰 좋은 부분 직사각형에 포함된 칸의 수를 구하도록 도와주자.

제한

테스트 세트당 시간 제한: 15초. 메모리 제한: 1GB. 1 ≤ T ≤ 50. 1 ≤ R ≤ 300. 1 ≤ C ≤ 300. 모든 i, j에 대해 0 ≤ $V_{i, j}$ ≤ $10^{3}$.

테스트 세트 1 (공개)

K = 0.

테스트 세트 2 (비공개)

0 ≤ K ≤ $10^{3}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 행의 수, 열의 수, 각 행에서 허용되는 두께 차이의 최댓값을 각각 나타내는 세 정수 R, C, K가 포함된 한 줄로 시작한다.

그다음에는 각각 C개의 정수를 포함하는 R개의 줄이 더 주어진다. r번째 줄의 c번째 정수는 r번째 행과 c번째 열에 있는 칸의 두께인 $V_{r, c}$이다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 좋은 부분 직사각형에 포함될 수 있는 칸 수의 최댓값이다.

추가 예제 - 테스트 세트 2

예제 케이스는 아래에 그림으로 나타나 있다. 각 케이스에서 칸 수가 가장 많은 좋은 부분 회로 기판은 초록색으로 강조되어 있다.