#include <cstdio>
#include <cstring>
int const MAX = 150;
int const MOD = 10000;
int n, m;

int a[MAX][MAX], dp[MAX][MAX];

int DFS(int x, int y)
{
    if(x > n || y > m || x < 1 || y < 1)
        return dp[x][y] = 0;
    if(dp[x][y])
        return dp[x][y];
    for(int i = 0; i <= a[x][y]; i++)
        for(int j = 0; i + j <= a[x][y]; j++)
            if(i || j)
                dp[x][y] = (dp[x][y] % MOD + DFS(x + i, y + j) % MOD) % MOD;
    return dp[x][y];
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                scanf("%d", &a[i][j]);
        memset(dp, 0, sizeof(dp));
        dp[n][m] = 1;
        printf("%d\n", DFS(1, 1));
    }
}