//从上到下从左向右扫一遍即可，类似一维硬币拼凑 

 1

//二维0-1背包

 2//dp[i+k][j+p]+=dp[i][j]; （计数dp）

 3//中等偏下题目 4#include<cstdio>

 5 #include<cstring>

 6 #include<algorithm>

 7 #define MAX 1000

 8 #define mod 10000

 9 using namespace std;

10 int dp[MAX][MAX];

11 int map[MAX][MAX];

12 int main()

13 {

14     int cas,m,n;

15     scanf("%d",&cas);

16     while(cas--)

17     {

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

19         for(int i=0;i<n;i++) for(int j=0;j<m;j++)

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

21         memset(dp,0,sizeof(dp));

22         dp[0][0]=1;

23         for(int i=0;i<n;i++)

24         {

25             for(int j=0;j<m;j++)

26             {

27                 for(int k=0;k<=map[i][j];k++)

28                 {

29                     for(int p=0;p<=(map[i][j]-k);p++)

30                     {

31                         if(k!=0||p!=0)

32                         {

33                             dp[i+k][j+p]+=dp[i][j];

34                             dp[i+k][j+p]%=mod;

35                         }

36                     }

37                 }

38             }

39         }

40         printf("%d\n",dp[n-1][m-1]);

41     }

42     return 0;

43 }