#include<bits/stdc++.h>
using namespace std;
int T;
int mp[10][10],vis[10][10];
int ans=-2e9;
int n,m;
const int dx[9]={-1,-1,-1,0,0,0,1,1,1},dy[9]={-1,0,1,-1,0,1,-1,0,1};
int check(int x,int y){
for(int i=0;i<9;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(vis[xx][yy]==1)
return 0;
}
return 1;
}
void dfs(int x,int y,int sum){
if(sum>=ans)ans=sum;
cout<<ans<<" ";
int xx=x+1,yy=y+1;
if(yy>m){
yy-=m;
xx+=1;
if(xx>n)return ;
}
else
{
if(check(xx,yy)==1)
{
vis[xx][yy]=1;
dfs(xx,yy,sum+mp[xx][yy]);
vis[xx][yy]=0;
}
else
dfs(xx,yy,sum);
}
}
int main(){
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
dfs(1,1,0);
dfs(1,1,mp[1][1]);
cout<<ans<<endl;
ans=-2e9;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
vis[i][j]=0;
mp[i][j]=0;
}
}
return 0;
}