K-Neutral Rectangles

Given an N × M rectangle of integers, find the area of the largest sub-rectangle such that, each cell of the sub-rectangle, Ri,j, is K-neutral cell. A cell, Ri,j, is K-neutral, if absolute difference between the values of Ri,j and each of its neighbors in horizontal and vertical direction is not more than K. The cells Ri−1,j, Ri+1,j, Ri,j−1 and Ri,j+1 are the four neighbors of the cell Ri,j. The neighborhoods should be considered only in the new sub-rectangle, not in the original rectangle. For example, 9 30 20 25 10 10 1 3 3 9 02347 1 7 11 10 8 For N = 4, M = 5 and K = 1 in the above rectangle, the largest K-neutral sub-rectangle is 133 234 Input Input starts with an integer T (≤ 100), denoting the number of test cases. Each test case starts with three integers N, M and K (1 ≤ N,M ≤ 1000, 0 ≤ K ≤ 100000). Each of the next N line will contain M integers Ri,j (0 ≤ Ri,j ≤ 10000000). Output For each case print the case number and the area of the largest K-neutral sub-rectangle. Sample Input 2 451 9 30 20 25 10 10 1 2 3 9 02347 1 7 11 10 8 221 13 46 Sample Output Case 1: 6 Case 2: 1