#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int HA = 1e4;

inline int read() {

    int x = , f = ; char c = getchar();

    while (c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while (c <= '' && c >= '') {x = x* + c-''; c = getchar();}

    return x * f;

}

int T, n, m, en[][], f[][];

bool vis[][];

inline int dfs(int x, int y) {

    if(x > n || y > m || x <  || y < ) return ;

    if(x == n && y == m) return ;

    if(vis[x][y] != false) return f[x][y];

    for(int i=; i<=en[x][y]; i++) {

        for(int j=; j+i<=en[x][y]; j++) {

            int xx = i + x, yy = j + y;

            if(xx == x && yy == y) continue;

            f[x][y] += dfs(xx, yy);

            if(f[x][y] >= HA) f[x][y] %= HA;

        }

    }

    vis[x][y] = true;

    return f[x][y];

}

int main() {

    T = read();

    while (T--) {

        memset(vis, , sizeof(vis));

        memset(f, , sizeof(f));

        n = read(), m = read();

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

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

                en[i][j] = read();

        printf("%d\n", dfs(, ) % HA);

    }

}