1 #include<stdio.h>
 2 #include<string.h>
 3 int n,m;
 4 int map[110][110];
 5 int dp[110][110];
 6 int dfs(int x,int y)
 7 {
 8     int sum=0,i,j;
 9     if(x==n&&y==m)
10         return 1;
11     if(dp[x][y]>=0)
12         return dp[x][y];
13     for(i=0; i<=map[x][y]; i++)
14         for(j=0; j<=map[x][y]; j++)
15         {
16             if((i+j)<=map[x][y]&&i+x<=n&&j+y<=m&&(i+j)!=0)
17             {
18                 sum+=dfs(i+x,j+y);
19                 sum%=10000;
20             }
21         }
22     dp[x][y]=sum;
23     return dp[x][y];
24 }
25 int main()
26 {
27     int t,i,j;
28     scanf("%d",&t);
29     while(t--)
30     {
31         scanf("%d%d",&n,&m);
32         for(i=1; i<=n; i++)
33             for(j=1; j<=m; j++)
34                 scanf("%d",&map[i][j]);
35         memset(dp,-1,sizeof(dp));
36         printf("%d\n",dfs(1,1));
37     }
38     return 0;
39 }