#include<bits/stdc++.h>
using namespace std;
int max(int a,int b,int c){
	if(a>b && a>c)
		return a;
	else if(b>a && b>c)
		return b;
	else
		return c;
}
 
int main(){
	int t;
	cin>>t;
	while(t--){
		int h,w;
		cin>>h>>w;
		int dp[h][w];
		for(int i=0;i<h;i++)
			for(int j=0;j<w;j++)
				cin>>dp[i][j];
		for(int i=1;i<h;i++){
			for(int j=0;j<w;j++){
					if(j==0)
					dp[i][j] = dp[i][j]+ std::max(dp[i-1][j],dp[i-1][j+1]);
					else if(j==w-1 && j-1>=0)
						dp[i][j] = dp[i][j] + std::max(dp[i-1][j],dp[i-1][j-1]);
					else
						dp[i][j] = dp[i][j] + max(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]);
			}
		}
		int ans=dp[h-1][0];
 
		for(int j=1;j<w;j++){
			if(dp[h-1][j]>ans)
				ans = dp[h-1][j];
		}
		cout<<ans<<"\n";
	}
	return 0;
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG1heChpbnQgYSxpbnQgYixpbnQgYyl7CglpZihhPmIgJiYgYT5jKQoJCXJldHVybiBhOwoJZWxzZSBpZihiPmEgJiYgYj5jKQoJCXJldHVybiBiOwoJZWxzZQoJCXJldHVybiBjOwp9CgppbnQgbWFpbigpewoJaW50IHQ7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pewoJCWludCBoLHc7CgkJY2luPj5oPj53OwoJCWludCBkcFtoXVt3XTsKCQlmb3IoaW50IGk9MDtpPGg7aSsrKQoJCQlmb3IoaW50IGo9MDtqPHc7aisrKQoJCQkJY2luPj5kcFtpXVtqXTsKCQlmb3IoaW50IGk9MTtpPGg7aSsrKXsKCQkJZm9yKGludCBqPTA7ajx3O2orKyl7CgkJCQkJaWYoaj09MCkKCQkJCQlkcFtpXVtqXSA9IGRwW2ldW2pdKyBzdGQ6Om1heChkcFtpLTFdW2pdLGRwW2ktMV1baisxXSk7CgkJCQkJZWxzZSBpZihqPT13LTEgJiYgai0xPj0wKQoJCQkJCQlkcFtpXVtqXSA9IGRwW2ldW2pdICsgc3RkOjptYXgoZHBbaS0xXVtqXSxkcFtpLTFdW2otMV0pOwoJCQkJCWVsc2UKCQkJCQkJZHBbaV1bal0gPSBkcFtpXVtqXSArIG1heChkcFtpLTFdW2otMV0sZHBbaS0xXVtqXSxkcFtpLTFdW2orMV0pOwoJCQl9CgkJfQoJCWludCBhbnM9ZHBbaC0xXVswXTsKCgkJZm9yKGludCBqPTE7ajx3O2orKyl7CgkJCWlmKGRwW2gtMV1bal0+YW5zKQoJCQkJYW5zID0gZHBbaC0xXVtqXTsKCQl9CgkJY291dDw8YW5zPDwiXG4iOwoJfQoJcmV0dXJuIDA7Cn0K

MQo2IDUKMyAxIDcgNCAyCjIgMSAzIDEgMQoxIDIgMiAxIDgKMiAyIDEgNSAzCjIgMSA0IDQgNAo1IDIgNyA1IDE=

1
6 5
3 1 7 4 2
2 1 3 1 1
1 2 2 1 8
2 2 1 5 3
2 1 4 4 4
5 2 7 5 1