1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define    MAX    105
 5 #define    MOD    10000
 6 
 7 int    main(void)
 8 {
 9     int    t,n,m;
10     int    s[MAX][MAX],dp[MAX][MAX];
11 
12     scanf("%d",&t);
13     while(t --)
14     {
15         memset(dp,0,sizeof(dp));
16 
17         scanf("%d%d",&n,&m);
18         for(int i = 1;i <= n;i ++)
19             for(int j = 1;j <= m;j ++)
20                 scanf("%d",&s[i][j]);
21 
22         dp[n][m] = 1;
23         for(int i = n;i >= 1;i --)
24             for(int j = m;j >= 1;j --)
25             {
26                 if(i == n && j == m)
27                     continue;
28                 else
29                     for(int r = 0;r <= s[i][j] && i + r <= n;r ++)
30                         for(int c = 0;c + r <= s[i][j] && j + c <= m;c ++)
31                             dp[i][j] = (dp[i][j] + dp[i + r][j + c]) % MOD;
32             }
33         printf("%d\n",dp[1][1]);
34     }
35 
36     return    0;
37 }