#include<iostream>
using namespace std;

int m,n;
int g[105][105],dp[105][105];

int Dfs(int a,int b)
{
    if(dp[a][b] != -1)
        return dp[a][b];
    int i,j,d,sum;
    d = g[a][b];
    sum = 0;
    for(i = 0;i <= d;i++)
    {
        for(j = 0;i+j <= d;j++)
        {
            if((i + j) == 0)
                continue;
            if(a+i <= m && b+j <= n)
            {
                sum += Dfs(a+i,b+j);
            }
            else
            {
                break;
            }
        }
    }
    sum = sum % 10000;
    dp[a][b] = sum;
    return dp[a][b];
}

int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(i=1; i <= m;i++)
            for(j = 1; j <= n;j++)
                scanf("%d",&g[i][j]);
        memset(dp,-1,sizeof(dp));
        dp[m][n] = 1;
        cout<<Dfs(1,1)<<endl;
    }
    return 0;
}