#include <stdio.h>
int p[501][501];
int max(int a, int b)
{
return (a > b ? a : b);
}
int main()
{
int times;
scanf("%d", ×);
while (times--)
{
int r, c, i, j;
scanf("%d %d", &r, &c);
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
{
scanf("%d", &p[i][j]);
}
}
/*
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
printf("%d ", p[i][j]);
printf("\n");
}
*/
// top row
for (j = 1; j < c ; j++)
p[0][j] += p[0][j-1];
// first column
for (i = 1; i < r ; i++)
p[i][0] += p[i-1][0];
// non boundary elements
for (i = 1; i < r ; i++)
{
for (j = 1; j < c ; j++)
{
p[i][j] += max(p[i-1][j], p[i][j-1]);
}
}
/*
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
printf("%d ", p[i][j]);
printf("\n");
}*/
i = r-1; j = c-1;
int min = 999;
while (i != 0 || j != 0)
{
if ( min > p[i][j]) min = p[i][j];
if (i > 0 && j > 0){
if ( p[i-1][j] > p[i][j-1] )
i = i - 1;
else j = j-1;
}
else{
if ( i == 0) j--;
else i--;
}
//printf("%d %d\n", i, j);
}
//printf("answer is %d\n", min);
if (min > 0 )
printf("%d\n", 1);
else
printf("%d\n", (0-min) +1);
}
//getch();
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CmludCBwWzUwMV1bNTAxXTsKaW50IG1heChpbnQgYSwgaW50IGIpCnsKICByZXR1cm4gKGEgPiBiID8gYSA6IGIpOyAgIAp9CmludCBtYWluKCkKewogICAgaW50IHRpbWVzOwogICAgc2NhbmYoIiVkIiwgJnRpbWVzKTsKICAgIAogICAgd2hpbGUgKHRpbWVzLS0pCiAgICB7CiAgICAgICAgICBpbnQgciwgYywgaSwgajsKICAgICAgICAgIHNjYW5mKCIlZCAlZCIsICZyLCAmYyk7CiAgICAgICAgICBmb3IgKGkgPSAwOyBpIDwgcjsgaSsrKQogICAgICAgICAgewogICAgICAgICAgICAgIGZvciAoaiA9IDA7IGogPCBjOyBqKyspCiAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICBzY2FuZigiJWQiLCAmcFtpXVtqXSk7CiAgICAgICAgICAgICAgfQogICAgICAgICAgfQogICAgICAgICAgLyogCiAgICAgICAgICBmb3IgKGkgPSAwOyBpIDwgcjsgaSsrKQogICAgICAgICAgewogICAgICAgICAgICAgIGZvciAoaiA9IDA7IGogPCBjOyBqKyspCiAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgIHByaW50ZigiJWQgIiwgcFtpXVtqXSk7CiAgICAgICAgICAgICAgcHJpbnRmKCJcbiIpOwogICAgICAgICAgfQogICAgICAgICAgKi8KICAgICAgICAgIAogICAgICAgICAgLy8gdG9wIHJvdwogICAgICAgICAgZm9yIChqID0gMTsgaiA8IGMgOyBqKyspCiAgICAgICAgICAgICAgcFswXVtqXSArPSBwWzBdW2otMV07IAogICAgICAgICAgLy8gZmlyc3QgY29sdW1uCiAgICAgICAgICBmb3IgKGkgPSAxOyBpIDwgciA7IGkrKykKICAgICAgICAgICAgICBwW2ldWzBdICs9IHBbaS0xXVswXTsKICAgICAgICAgIAogICAgICAgICAgLy8gbm9uIGJvdW5kYXJ5IGVsZW1lbnRzCiAgICAgICAgICBmb3IgKGkgPSAxOyBpIDwgciA7IGkrKykKICAgICAgICAgIHsKICAgICAgICAgICAgICBmb3IgKGogPSAxOyBqIDwgYyA7IGorKykKICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgIHBbaV1bal0gKz0gbWF4KHBbaS0xXVtqXSwgcFtpXVtqLTFdKTsKICAgICAgICAgICAgICB9CiAgICAgICAgICB9CiAgICAgICAgICAgLyogICAgIAogICAgICAgICAgZm9yIChpID0gMDsgaSA8IHI7IGkrKykKICAgICAgICAgIHsKICAgICAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgYzsgaisrKQogICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICBwcmludGYoIiVkICIsIHBbaV1bal0pOwogICAgICAgICAgICAgIHByaW50ZigiXG4iKTsKICAgICAgICAgIH0qLwogICAgICAgICBpID0gci0xOyBqID0gYy0xOwogICAgICAgICBpbnQgbWluID0gOTk5OwogICAgICAgICB3aGlsZSAoaSAhPSAwIHx8IGogIT0gMCkKICAgICAgICAgewogICAgICAgICAgICAgICBpZiAoIG1pbiA+IHBbaV1bal0pIG1pbiA9IHBbaV1bal07CiAgICAgICAgICAgICAgIGlmIChpID4gMCAmJiBqID4gMCl7CiAgICAgICAgICAgICAgICAgICAgIGlmICggcFtpLTFdW2pdID4gcFtpXVtqLTFdICApCiAgICAgICAgICAgICAgICAgICAgICAgICAgaSA9IGkgLSAxOwogICAgICAgICAgICAgICAgICAgICBlbHNlIGogPSBqLTE7CiAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKCBpID09IDApIGotLTsKICAgICAgICAgICAgICAgICAgICAgICAgICBlbHNlICAgaS0tOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAvL3ByaW50ZigiJWQgJWRcbiIsIGksIGopOwogICAgICAgICB9CiAgICAgICAgIAogICAgICAgICAvL3ByaW50ZigiYW5zd2VyIGlzICVkXG4iLCBtaW4pOwogICAgICAgICAKICAgICAgICAgIGlmIChtaW4gPiAwICApCiAgICAgICAgICBwcmludGYoIiVkXG4iLCAxKTsKICAgICAgICAgIGVsc2UgCiAgICAgICAgICBwcmludGYoIiVkXG4iLCAoMC1taW4pICsxKTsKICAgIH0KICAgIC8vZ2V0Y2goKTsKICAgIHJldHVybiAwOwp9Cg==