#include #include #include #include #include #include #include #include #include #include #include #include #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define LL long long #define ull unsigned int #define INF 0x7FFFFFFF//or 0x3f3f3f3f ? using namespace std; template inline void read(T& x) { int f = 1; x = 0; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } /*============ Header Template ============*/ const int N = 1000 + 10; int n, m, L[N][N], R[N][N], U[N][N], D[N][N]; ull Ans, k[N][N], p[N][N], g[N], s[N]; int q[N], top; int main() { REP(i, 1, 1000) g[i] = g[i - 1] + i * i; REP(i, 1, 1000) s[i] = s[i - 1] + i; REP(i, 1, 1000) PER(j, i, 1) p[i][j] = p[i][j + 1] + j * (i + 1 - j); int T; read(T); while (T--) { read(n); read(m); REP(i, 1, n) REP(j, 1, m) read(k[i][j]); REP(i, 1, n) { q[top = 0] = 0; REP(j, 1, m) { while (top && k[i][q[top]] > k[i][j]) top--; L[i][j] = j - q[top], q[++top] = j; } } REP(i, 1, n) { q[top = 0] = m + 1; PER(j, m, 1) { while (top && k[i][q[top]] > k[i][j]) top--; R[i][j] = q[top] - j, q[++top] = j; } } REP(j, 1, m) { q[top = 0] = 0; REP(i, 1, n) { while (top && k[q[top]][j] < k[i][j]) top--; U[i][j] = i - q[top], q[++top] = i; } } REP(j, 1, m) { q[top = 0] = n + 1; PER(i, n, 1) { while (top && k[q[top]][j] < k[i][j]) top--; D[i][j] = q[top] - i, q[++top] = i; } } Ans = 0; REP(i, 1, n) REP(j, 1, m) { int a = min(L[i][j], R[i][j]), b = max(L[i][j], R[i][j]); int c = min(U[i][j], D[i][j]), d = max(U[i][j], D[i][j]); Ans += k[i][j] * (g[a] + (s[b - 1] - s[a]) * a + p[a + b - 1][b]) * (g[c] + (s[d - 1] - s[c]) * c + p[c + d - 1][d]); } printf("%u\n", Ans); } return 0; }