#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<vector>

#include<iterator>

#include<utility>

#include<sstream>

#include<iostream>

#include<cmath>

#include<stack>

using namespace std;

const int INF=1000000007;

const double eps=0.00000001;

int row,col,maze[101][101];

int dp[101][101];

const int mod=10000;

int dfs(int x,int y)

{

    if(x==row-1&&y==col-1)  return 1;   //到达终点

    int& ret=dp[x][y];                  //记忆化

    if(ret!=-1)  return ret;

    ret=0;

    for(int stx=x;stx<=x+maze[x][y]&&stx<row;stx++)    //每一行找

        for(int sty=y;stx+sty<=x+y+maze[x][y]&&sty<col;sty++)  //每一列

    {

        if(stx!=x||sty!=y)    //排除自己

        {

            ret+=dfs(stx,sty);

            ret%=mod;

        }

    }

    return ret%mod;

}

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        cin>>row>>col;

        for(int i=0;i<row;i++)

            for(int j=0;j<col;j++)  scanf("%d",&maze[i][j]);

        memset(dp,-1,sizeof(dp));

        int ans=dfs(0,0);

        cout<<ans<<endl;

    }

    return 0;

}