#include <iostream>
#include <cstring>
using namespace std;
int h;
int w;
int x[101][101];
int dp[101][101];
const int INF = 1e9;
int rec(int i,int j){
    if(i==h-1){
        return x[i][j];
    }
    if(dp[i][j]!=-1){
        return dp[i][j];
    }
    int res=-INF;
    if(i + 1 < h){
        res=max(res,rec(i+1,j)+x[i][j]);

        if(j + 1 < w) {
            res=max(res,rec(i+1,j+1)+x[i][j]);
        }

        if(j - 1 >= 0) {
            res=max(res,rec(i+1,j-1)+x[i][j]);
        }
    }
    dp[i][j]=res;
    return res;
}
int main()
{
    int t;
    cin>>t;
    int a;
    for(int i = 0;i<t;i++){
        cin>>h>>w;
        a=0;
        memset(dp,-1,sizeof dp);
        for(int j = 0;j<h;j++){
            for(int k = 0;k<w;k++){
                cin>>x[j][k];
            }
        }
        for(int l = 0;l<w;l++){
            a=max(a,rec(0,l));
        }
        cout<<a << endl;
    }
    return 0;
}