单调队列
把每列的最大值最小值预处理出来，压成一维用两个单调队列维护最大值最小值，和最左下表。
当队首元素相减不满足约束时出队，这个时候维护最小左下表，让它移动到两个队列中队首靠左的下表那继续更新答案。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
#define FAST_IO ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
inline int lowbit(int x){ return x & (-x); }
inline int read(){int ret = 0, w = 0; char ch = 0;while(!isdigit(ch)){w |= ch == '-', ch = getchar();}while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ 48);ch = getchar();}return w ? -ret : ret;
}
inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }
template <typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){A ans = 1;for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;return ans;
}
const int N = 1000;
int _, n, m, a[N][N], mx[N], mn[N], q1[N], q2[N], ans;
int main(){for(_ = read(); _; _ --){ans = 0;n = read(), m = read();for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++) a[i][j] = read();}for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++){mx[j] = 0, mn[j] = INF;}for(int t = i; t <= n; t ++){for(int j = 1; j <= n; j ++){mx[j] = max(mx[j], a[t][j]);mn[j] = min(mn[j], a[t][j]);}int l1 = 1, r1 = 0, l2 = 1, r2 = 0, sgm = 1;for(int j = 1; j <= n; j ++){while(l1 <= r1 && mx[q1[r1]] <= mx[j]) r1 --;q1[++r1] = j;while(l2 <= r2 && mn[q2[r2]] >= mn[j]) r2 --;q2[++r2] = j;while(l1 <= r1 && l2 <= r2 && mx[q1[l1]] - mn[q2[l2]] > m){if(q1[l1] == sgm) l1 ++;if(q2[l2] == sgm) l2 ++;sgm ++;}ans = max(ans, (j - sgm + 1) * (t - i + 1));}}}printf("%d\n", ans);}return 0;
}