import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class MAGRID {
    static int[][] a = new int[510][510];
    static boolean[][] v = new boolean[510][510];
    static int R, C;

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            R = in.nextInt();
            C = in.nextInt();
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++)
                    a[i][j] = in.nextInt();
            long lo = 1;
            long hi = 250000010;
            long mid;
            long cst;
            int i, j;
            long ans;
            while (lo < hi) {
                PriorityQueue<state> pq = new PriorityQueue<state>();
                for (i = 0; i < R; i++)
                    for (j = 0; j < C; j++)
                        v[i][j] = false;
                mid = (lo + hi) / 2;
                pq.add(new state(0, 0, mid));
                state cur;
                ans = -1;
                while (!pq.isEmpty()) {
                    cur = pq.poll();
                    cst = cur.cst;
                    i = cur.i;
                    j = cur.j;
                    if (i == R - 1 && j == C - 1) {
                        ans = cst;
                        break;
                    }
                    v[i][j] = true;
                    if (i + 1 < R && !v[i + 1][j] && cst + a[i + 1][j] > 0)
                        pq.add(new state(i + 1, j, cst + a[i + 1][j]));
                    if (j + 1 < C && !v[i][j + 1] && cst + a[i][j + 1] > 0)
                        pq.add(new state(i, j + 1, cst + a[i][j + 1]));
                }
                if (ans <= 0) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            System.out.println(lo);
        }
    }

    static class state implements Comparable<state> {
        int i, j;
        long cst;

        public state(int ii, int jj, long cost) {
            cst = cost;
            i = ii;
            j = jj;
        }

        @Override
        public int compareTo(state o) {
            if (o.cst < cst)
                return -1;
            if (o.cst > cst)
                return 1;
            return 0;
        }

    }

    // private static long solve(int i, int j) {
    // if(i>=R||i<0||j>=C||j<0)return 0;
    // if(i==R-1&&j==C-1)return a[i][j];
    // if(dp[i][j]!=-1)
    // return dp[i][j];
    // long max = Integer.MIN_VALUE;
    // max = Math.max(max, solve(i+1,j)+a[i][j]);
    // max = Math.max(max, solve(i,j+1)+a[i][j]);
    // return dp[i][j]=max;
    // }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}