import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class BYTESM2 {
// TODO Auto-generated method stub
int t
= Integer.
parseInt(br.
readLine()); StringBuilder sb = new StringBuilder();
while (t-- > 0) {
int h
= Integer.
parseInt(st.
nextToken()); int w
= Integer.
parseInt(st.
nextToken()); int array[][] = new int[h][w];
//int answer[][] = new int[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
array
[i
][j
] = Integer.
parseInt(st.
nextToken()); }
}
//for (int i = 0; i < w; i++) {
//answer[0][i] = array[0][i];
//}
//br.readLine();
for (int i = 1; i < h; i++) {
for (int j = 0; j < w; j++) {
int a = 0, b = 0, c = 0;
if (j >= 1)
a = array[i - 1][j - 1];
if (j + 1 < w)
c = array[i - 1][j + 1];
b = array[i - 1][j];
array
[i
][j
] += Math.
max(a,
Math.
max(b, c
)); }
}
for (int i = 0; i < w; i++) {
if (max < array[array.length - 1][i])
max = array[array.length - 1][i];
}
sb.append(max + "\n");
}
}
}
aW1wb3J0IGphdmEuaW8uQnVmZmVyZWRSZWFkZXI7CmltcG9ydCBqYXZhLmlvLklPRXhjZXB0aW9uOwppbXBvcnQgamF2YS5pby5JbnB1dFN0cmVhbVJlYWRlcjsKaW1wb3J0IGphdmEudXRpbC5TdHJpbmdUb2tlbml6ZXI7CgpjbGFzcyBCWVRFU00yIHsKCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB0aHJvd3MgTnVtYmVyRm9ybWF0RXhjZXB0aW9uLCBJT0V4Y2VwdGlvbiB7CgkJLy8gVE9ETyBBdXRvLWdlbmVyYXRlZCBtZXRob2Qgc3R1YgoJCUJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKCQlpbnQgdCA9IEludGVnZXIucGFyc2VJbnQoYnIucmVhZExpbmUoKSk7CgkJU3RyaW5nQnVpbGRlciBzYiA9IG5ldyBTdHJpbmdCdWlsZGVyKCk7CgkJd2hpbGUgKHQtLSA+IDApIHsKCQkJU3RyaW5nVG9rZW5pemVyIHN0ID0gbmV3IFN0cmluZ1Rva2VuaXplcihici5yZWFkTGluZSgpKTsKCQkJaW50IGggPSBJbnRlZ2VyLnBhcnNlSW50KHN0Lm5leHRUb2tlbigpKTsKCQkJaW50IHcgPSBJbnRlZ2VyLnBhcnNlSW50KHN0Lm5leHRUb2tlbigpKTsKCQkJaW50IGFycmF5W11bXSA9IG5ldyBpbnRbaF1bd107CgkJCS8vaW50IGFuc3dlcltdW10gPSBuZXcgaW50W2hdW3ddOwoJCQlmb3IgKGludCBpID0gMDsgaSA8IGg7IGkrKykgewoJCQkJc3QgPSBuZXcgU3RyaW5nVG9rZW5pemVyKGJyLnJlYWRMaW5lKCkpOwoJCQkJZm9yIChpbnQgaiA9IDA7IGogPCB3OyBqKyspIHsKCQkJCQlhcnJheVtpXVtqXSA9IEludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpOwoJCQkJfQoJCQl9CgkJCS8vZm9yIChpbnQgaSA9IDA7IGkgPCB3OyBpKyspIHsKCQkJCS8vYW5zd2VyWzBdW2ldID0gYXJyYXlbMF1baV07CgkJCS8vfQoJCQkvL2JyLnJlYWRMaW5lKCk7CgkJCWZvciAoaW50IGkgPSAxOyBpIDwgaDsgaSsrKSB7CgoJCQkJZm9yIChpbnQgaiA9IDA7IGogPCB3OyBqKyspIHsKCQkJCQlpbnQgYSA9IDAsIGIgPSAwLCBjID0gMDsKCQkJCQlpZiAoaiA+PSAxKQoJCQkJCQlhID0gYXJyYXlbaSAtIDFdW2ogLSAxXTsKCQkJCQlpZiAoaiArIDEgPCB3KQoJCQkJCQljID0gYXJyYXlbaSAtIDFdW2ogKyAxXTsKCQkJCQliID0gYXJyYXlbaSAtIDFdW2pdOwoJCQkJCWFycmF5W2ldW2pdICs9IE1hdGgubWF4KGEsIE1hdGgubWF4KGIsIGMpKTsKCQkJCX0KCQkJfQoJCQlpbnQgbWF4ID0gSW50ZWdlci5NSU5fVkFMVUU7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgdzsgaSsrKSB7CgkJCQlpZiAobWF4IDwgYXJyYXlbYXJyYXkubGVuZ3RoIC0gMV1baV0pCgkJCQkJbWF4ID0gYXJyYXlbYXJyYXkubGVuZ3RoIC0gMV1baV07CgkJCX0KCQkJc2IuYXBwZW5kKG1heCArICJcbiIpOwoJCX0KCQlTeXN0ZW0ub3V0LnByaW50bG4oc2IpOwoJfQoKfQoK