/*

 ZOJ 3213

 好吧，看过那种括号表示法后，就崩溃了，实在受不了。情况复杂，写了两天，人也有点傻X了，只能放弃，转而用最小表示法。

 最小表示法不难写：

  1）首先，要承认路径上有格子不选的情况，于是，在00的情况下，可扩展，也可不选。

  2）不能出现环，因而不能有L=U的情况出现。

  3）以下是模版代码，类同是必然。但转而求路径数的时候，应当去掉不扩展的情况，同时，在IF(L|U)的情况下，亦不必考虑当前是否为最后一个格子，

     只需按写的转移即可。

  4）增加独立插头时，必须在总的独立插头数小于2的情况下进行。

   注意：之所以不能出现两个插头，是因为，独立插头是单向的路径，不能进了又出。限制这个条件是非常有必要的。而在此处我本以为若限制了条件就得不出

   最优解，而其实，因为存在不选的状态，限制了这个条件依然是可以有最优解的。

 */

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 const int MAXD=;

 const int HASH=;

 const int STATE=;

 int N,M;

 int maze[MAXD][MAXD];

 int code[MAXD];

 int ch[MAXD];

 int num;

 int ans;

 struct HASHMAP

 {

     int head[HASH],next[STATE],size;

     int state[STATE],dp[STATE];

     void init()

     {

         size=;

         memset(head,-,sizeof(head));

     }

     void push(int st,int ans)

     {

         int i,h=st%HASH;

         for(i=head[h];i!=-;i=next[i])

           if(state[i]==st)

           {

               if(dp[i]<ans)dp[i]=ans;

               return;

           }

         state[size]=st;

         dp[size]=ans;

         next[size]=head[h];

         head[h]=size++;

     }

 }hm[];

 void decode(int *code,int m,int st)

 {

     num=st&;//??????

     st>>=;

     for(int i=m;i>=;i--)

     {

         code[i]=st&;

         st>>=;

     }

 }

 int encode(int *code,int m)

 {

     int cnt=;

     memset(ch,-,sizeof(ch));

     ch[]=;

     int st=;

     for(int i=;i<=m;i++)

     {

         if(ch[code[i]]==-)ch[code[i]]=cnt++;

         code[i]=ch[code[i]];

         st<<=;

         st|=code[i];

     }

     st<<=;

     st|=num;

     return st;

 }

 void shift(int *code,int m)

 {

     for(int i=m;i>;i--)code[i]=code[i-];

     code[]=;

 }

 void dpblank(int i,int j,int cur)

 {

     int k,left,up;

     for(k=;k<hm[cur].size;k++)

     {

         decode(code,M,hm[cur].state[k]);

         left=code[j-];

         up=code[j];

         if(left&&up)

         {

             if(left!=up)

             {

                 code[j-]=code[j]=;

                 for(int t=;t<=M;t++)

                   if(code[t]==up)

                      code[t]=left;

                 if(j==M)shift(code,M);

                 hm[cur^].push(encode(code,M),hm[cur].dp[k]+maze[i][j]);

             }

         }

         else if(left||up)

         {

             int t;

             if(left)t=left;

             else t=up;

             if(maze[i][j+])

             {

                 code[j-]=;

                 code[j]=t;

                 hm[cur^].push(encode(code,M),hm[cur].dp[k]+maze[i][j]);

             }

             if(maze[i+][j])

             {

                 code[j-]=t;

                 code[j]=;

                hm[cur^].push(encode(code,j==M?M-:M),hm[cur].dp[k]+maze[i][j]);

             }

             if(num<)   //封住一端，增加一个独立插头。

             {

                 num++;

                 code[j-]=code[j]=;

                 hm[cur^].push(encode(code,j==M?M-:M),hm[cur].dp[k]+maze[i][j]);

             }

         }

         else

         {

             code[j-]=code[j]=;      //讨论简单路径，只需不讨论不选的情况就可以了。

            hm[cur^].push(encode(code,j==M?M-:M),hm[cur].dp[k]);

             if(maze[i][j+]&&maze[i+][j])

             {

                 code[j-]=code[j]=;

                 hm[cur^].push(encode(code,M),hm[cur].dp[k]+maze[i][j]);

             }

             if(num<)

             {

                 num++;

                 if(maze[i][j+])

                 {

                     code[j]=;

                     code[j-]=;

                     hm[cur^].push(encode(code,M),hm[cur].dp[k]+maze[i][j]);

                 }

                 if(maze[i+][j])

                 {

                     code[j-]=;

                     code[j]=;

                    hm[cur^].push(encode(code,j==M?M-:M),hm[cur].dp[k]+maze[i][j]);

                 }

             }

         }

     }

 }

 void dpblock(int i,int j,int cur)

 {

     int k;

     for(k=;k<hm[cur].size;k++)

     {

         decode(code,M,hm[cur].state[k]);//?????!!!

         code[j-]=code[j]=;

         if(j==M)shift(code,M);

         hm[cur^].push(encode(code,M),hm[cur].dp[k]);

     }

 }

 void init()

 {

     scanf("%d%d",&N,&M);

     ans=;

     memset(maze,,sizeof(maze));//???????

     for(int i=;i<=N;i++)

       for(int j=;j<=M;j++)

       {

           scanf("%d",&maze[i][j]);

           if(maze[i][j]>ans)ans=maze[i][j];

       }

 }

 void solve()

 {

     int i,j,cur=;

     hm[cur].init();

     hm[cur].push(,);

     for(i=;i<=N;i++)

        for(int j=;j<=M;j++)

        {

            hm[cur^].init();

            if(maze[i][j])dpblank(i,j,cur);

            else dpblock(i,j,cur);

            cur^=;

        }

     for(i=;i<hm[cur].size;i++)

       if(hm[cur].dp[i]>ans)

         ans=hm[cur].dp[i];

     printf("%d\n",ans);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         init();

         solve();

     }

     return ;

 }

 #include <iostream>

 #include <stdio.h>

 #include <cstring>

 using namespace std;

 const int MAXD=;

 const int MAXL=;

 const int MAXH=;

 int n,m;

 int ans; int num;

 int map[MAXD][MAXD];

 int code[MAXD]; int pos[MAXD],stac[MAXD];

 int tmp[MAXD];

 struct HASHMAP{

     int hash[MAXL],state[MAXH],next[MAXH];

     int f[MAXH];

     int size;

     void init(){

         size=;

         memset(hash,-,sizeof(hash));

     }

     void push(int st,int anst) {

         int h=st%MAXL;

         for(int i=hash[h];i!=-;i=next[i]){

             if(state[i]==st){

                 if(f[i]<anst){

                     f[i]=anst;

                 }

                 return ;

             }

         }

         state[size]=st;

         f[size]=anst;

         next[size]=hash[h];

         hash[h]=size++;

     }

 }hm[];

 void decode(int st){

     for(int i=m;i>=;i--){

         int t=st&;

         code[i]=t;

         st=st>>;

     }

 }

 int fd_r(int j){

     int top=-;

     for(int i=;i<=m;i++){

         if(code[i]==) continue;

         else if(code[i]==){

             ++top;

             pos[top]=i; stac[top]=code[i];

         }

         else if(code[i]==){

             if(pos[top]==j) return i;

             else top--;

         }

     }

 }

 int fd_l(int j){

     int top=-;

     for(int i=;i<=m;i++){

         if(code[i]==) continue;

         else if(code[i]==){

             ++top;

             pos[top]=i; stac[top]=code[i];

         }

         else if(code[i]==){

             if(i==j) return pos[top];

             else top--;

         }

     }

 }

 void dpblank(int i,int j,int cur){

     int em;int tmpst; int ls,us,tts;

     for(int e=;e<hm[cur].size;e++){

         int st=hm[cur].state[e];

         num=st&;

         st>>=;

         decode(st);

         int left=code[j-],up=code[j];

         ls=(m-j+)*;  us=(m-j)*;

         if(!left&&!up){

             tmpst=(st^(left<<ls))^(up<<us);

             if(j==m) tmpst=tmpst>>;

             tmpst<<=;

             tmpst|=num;

             hm[cur^].push(tmpst,hm[cur].f[e]);

             if(map[i+][j]>&&map[i][j+]>){

                 tmpst=(st^(left<<ls))^(<<ls);

                 tmpst=(tmpst^(up<<us))^(<<us);

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             if(num<){

                 num++;

                 if(map[i][j+]>){

                     tmpst=(st^(left<<ls));

                     tmpst=(tmpst^(up<<us))^(<<us);

                     tmpst<<=;

                     tmpst|=num;

                     hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

                 }

                 if(map[i+][j]>){

                     tmpst=(st^(left<<ls))^(<<ls);

                     tmpst=(tmpst^(up<<us));

                     if(j==m) tmpst>>=;

                     tmpst<<=;

                     tmpst|=num;

                     hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

                 }

             }

         }

         else if(left&&up){

             if(left==&&up==){

                 int tt=fd_r(j);

                 tts=(m-tt)*;

                 tmpst=(st^(code[tt]<<tts))^(<<tts);

                 tmpst=(tmpst^(left<<ls));

                 tmpst=(tmpst^(up<<us));

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             else if(left==&&up==){

                 int tt=fd_l(j-);

                 tts=(m-tt)*;

                 tmpst=(st^(code[tt]<<tts))^(<<tts);

                 tmpst=(tmpst^(left<<ls));

                 tmpst=(tmpst^(up<<us));

                 if(j==m) tmpst>>=;

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             else if(left==&&up==){

                 tmpst=(st^(left<<ls));

                 tmpst=(tmpst^(up<<us));

                 if(j==m) tmpst>>=;

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             else if(left==&&up==){

                 tmpst=(st^(left<<ls));

                 tmpst=(tmpst^(up<<us));

                 if(j==m) tmpst>>=;

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             else if(left==&&up!=){

                 int tt;

                 if(up==) tt=fd_r(j);

                 else tt=fd_l(j);

                 tts=(m-tt)*;

                 tmpst=st^(left<<ls);

                 tmpst=tmpst^(up<<us);

                 tmpst=(tmpst^(code[tt]<<tts))^(<<tts);

                 if(j==m) tmpst>>=;

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             else if(left!=&&up==){

                 int tt;

                 if(left==) tt=fd_r(j-);

                 else tt=fd_l(j-);

                 tts=(m-tt)*;

                 tmpst=st^(left<<ls);

                 tmpst=tmpst^(up<<us);

                 tmpst=(tmpst^(code[tt]<<tts))^(<<tts);

                 if(j==m) tmpst>>=;

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

         }

         else{

             int tt,cott;

             if(left) tt=left;

             else tt=up;

             if(map[i][j+]>){

                 tmpst=st^(up<<us)^(tt<<us);

                 tmpst=tmpst^(left<<ls);

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             if(map[i+][j]>){

                 tmpst=st^(left<<ls)^(tt<<ls);

                 tmpst=tmpst^(up<<us);

                 if(j==m)  tmpst>>=;

                 tmpst<<=;

                 tmpst|=num;

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             if(tt==&&num<){    //忘了限制条件<2，WA了N久。

                 tmpst=st^(left<<ls)^(up<<us);

                 if(j==m)  tmpst>>=;

                 tmpst<<=;

                 tmpst|=(num+);

                 hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

             if(left!=&&up!=&&num<){

             int sp=(tt==left? j-: j);

             tts=(m-sp)*;

             if(tt==) cott=fd_r(sp);

             else cott=fd_l(sp);

             tmpst=st^(code[sp]<<tts)^(code[cott]<<((m-cott)*))^(<<((m-cott)*));

             if(j==m) tmpst>>=;

             num++;

             tmpst<<=;

             tmpst|=num;

             hm[cur^].push(tmpst,hm[cur].f[e]+map[i][j]);

             }

         }

     }

 }

 void dpblock(int i,int j,int cur){

     int em; int tmpst;

     for(int k=;k<hm[cur].size;k++){

         int st=hm[cur].state[k];

         num=st&;

         st>>=;

         decode(st);

         tmpst=st^(code[j]<<((m-j)*))^(code[j-]<<((m-j+)*));

         if(j==m)  tmpst>>=;

         tmpst<<=;

         tmpst|=num;

         hm[cur^].push(tmpst,hm[cur].f[k]);

     }

 }

 void solve(){

     int cur=,i;

     hm[cur].init();

     hm[cur].push(,);

     for( i=;i<=n;i++){

         for(int j=;j<=m;j++){

             hm[cur^].init();

             if(map[i][j]>) dpblank(i,j,cur);

             else dpblock(i,j,cur);

             cur=cur^;

         }

     }

     for( i=;i<hm[cur].size;i++)

         if(hm[cur].f[i]>ans) ans=hm[cur].f[i];

     printf("%d\n",ans);

 }

 int main(){

     int T; int i,j;

     scanf("%d",&T);

     while(T--){

         ans=;

         scanf("%d%d",&n,&m);

         memset(map,,sizeof(map));

         for(i=;i<=n;i++){

             for(j=;j<=m;j++){

                 scanf("%d",&map[i][j]);

                 if(map[i][j]>ans) ans=map[i][j];

             }

         }

         solve();

     }

     return ;

 }