#include #define inf 1234567890123456789LL using namespace std; using cat = long long; int main() { cin.sync_with_stdio(0); cin.tie(0); int T; cin >> T; for(int t = 0; t < T; t++) { int N, M; cin >> N >> M; vector< vector > G(N, vector(M)); for(int i = 0; i < N*M; i++) cin >> G[i/M][i%M]; // compute max. sums from each central cell in all directions vector< vector > mx_up(N, vector(M)); vector< vector > mx_down(N, vector(M)); vector< vector > mx_lft(N, vector(M)); vector< vector > mx_rt(N, vector(M)); for(int i = 0; i < N; i++) { cat mi = 0, sum = 0; for(int j = 0; j < M; j++) { if(j > 0) mx_lft[i][j] = sum-mi; mi = min(mi, sum); sum += G[i][j]; } mi = sum = 0; for(int j = M-1; j >= 0; j--) { if(j < M-1) mx_rt[i][j] = sum-mi; mi = min(mi, sum); sum += G[i][j]; } } for(int i = 0; i < M; i++) { cat mi = 0, sum = 0; for(int j = 0; j < N; j++) { if(j > 0) mx_up[j][i] = sum-mi; mi = min(mi, sum); sum += G[j][i]; } mi = sum = 0; for(int j = N-1; j >= 0; j--) { if(j < N-1) mx_down[j][i] = sum-mi; mi = min(mi, sum); sum += G[j][i]; } } cat ans = -inf; // bruteforce all central cells for(int i = 1; i < N-1; i++) for(int j = 1; j < M-1; j++) { cat sum = G[i][j] + mx_down[i][j] + mx_up[i][j] + mx_lft[i][j] + mx_rt[i][j]; ans = max(ans, sum); } cout << ans << "\n"; } return 0; }