#include <bits/stdc++.h>
#define ll long long
#define PI 3.14159265359
#define DP(x, y) memset(x, y, sizeof x)
#define all(x) x.begin(), x.end()
#define read(x) freopen("x", "r", stdin);
#define write(x) freopen("x", "w", stdout);
using namespace std;
ll gcd(ll a,ll b) { while(b) { ll x = a; a = b; b = x % b; } return a; }
ll lcm(ll a,ll b) { return a / gcd(a, b) * b; }
ll nC2(ll n) { return (n)*(n-1)/2; }
ll summing(ll n) { return (n)*(n+1); }
int Paths(int i, int j, int n, int m, vector<vector<char>>&grid, vector<vector<bool>>&vis, vector<vector<int>>&dp) {
if (i == n && j == m) {
return 1;
}
if (i > n || j > m || i == 0 || j == 0) {
return 0;
}
if ( grid[i][j] == '*' || vis[i][j] ) {
return 0;
}
if (~dp[i][j]) {
return dp[i][j];
}
vis[i][j] = 1;
int x = Paths(i+1, j, n, m, grid, vis, dp);
int y = Paths(i, j+1, n, m, grid, vis, dp);
int z = Paths(i-1, j, n, m, grid, vis, dp);
int w = Paths(i, j-1, n, m, grid, vis, dp);
vis[i][j] = 0;
return (dp[i][j] = x+y+z+w);
}
void solve() {
int n,m; cin >> n >> m;
vector<pair<int,int>> breaking;
vector<vector<char>> grid(n+1, vector<char>(m+1, '.'));
vector<vector<bool>> vis(n+1, vector<bool>(m+1, 0));
vector<vector<int>> dp(n+1, vector<int>(m+1, -1));
cin.ignore();
for (int i=0; i<n; i++) {
string s, row, col;
getline(cin, s);
stringstream ss(s);
ss >> row;
while (ss >> col) {
breaking.push_back({stoi(row), stoi(col)});
}
}
for (auto i:breaking) {
grid[i.first][i.second] = '*';
}
cout << Paths(1,1,n,m,grid,vis,dp) << "\n\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
ll t=1; cin >> t;
while (t--) { solve(); }
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgUEkgMy4xNDE1OTI2NTM1OQojZGVmaW5lIERQKHgsIHkpIG1lbXNldCh4LCB5LCBzaXplb2YgeCkKI2RlZmluZSBhbGwoeCkgeC5iZWdpbigpLCB4LmVuZCgpCiNkZWZpbmUgcmVhZCh4KSBmcmVvcGVuKCJ4IiwgInIiLCBzdGRpbik7CiNkZWZpbmUgd3JpdGUoeCkgZnJlb3BlbigieCIsICJ3Iiwgc3Rkb3V0KTsKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpsbCBnY2QobGwgYSxsbCBiKSB7IHdoaWxlKGIpIHsgbGwgeCA9IGE7IGEgPSBiOyBiID0geCAlIGI7IH0gcmV0dXJuIGE7IH0KbGwgbGNtKGxsIGEsbGwgYikgeyByZXR1cm4gYSAvIGdjZChhLCBiKSAqIGI7IH0KbGwgbkMyKGxsIG4pIHsgcmV0dXJuIChuKSoobi0xKS8yOyB9CmxsIHN1bW1pbmcobGwgbikgeyByZXR1cm4gKG4pKihuKzEpOyB9CgppbnQgUGF0aHMoaW50IGksIGludCBqLCBpbnQgbiwgaW50IG0sIHZlY3Rvcjx2ZWN0b3I8Y2hhcj4+JmdyaWQsIHZlY3Rvcjx2ZWN0b3I8Ym9vbD4+JnZpcywgdmVjdG9yPHZlY3RvcjxpbnQ+PiZkcCkgewoKICAgIGlmIChpID09IG4gJiYgaiA9PSBtKSB7CiAgICAgICAgcmV0dXJuIDE7CiAgICB9CiAgICBpZiAoaSA+IG4gfHwgaiA+IG0gfHwgaSA9PSAwIHx8IGogPT0gMCkgewogICAgICAgIHJldHVybiAwOwogICAgfQogICAgaWYgKCBncmlkW2ldW2pdID09ICcqJyB8fCB2aXNbaV1bal0gKSB7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CiAgICBpZiAofmRwW2ldW2pdKSB7CiAgICAgICAgcmV0dXJuIGRwW2ldW2pdOwogICAgfQoKICAgIHZpc1tpXVtqXSA9IDE7CiAgICBpbnQgeCA9IFBhdGhzKGkrMSwgaiwgbiwgbSwgZ3JpZCwgdmlzLCBkcCk7CiAgICBpbnQgeSA9IFBhdGhzKGksIGorMSwgbiwgbSwgZ3JpZCwgdmlzLCBkcCk7CiAgICBpbnQgeiA9IFBhdGhzKGktMSwgaiwgbiwgbSwgZ3JpZCwgdmlzLCBkcCk7CiAgICBpbnQgdyA9IFBhdGhzKGksIGotMSwgbiwgbSwgZ3JpZCwgdmlzLCBkcCk7CiAgICB2aXNbaV1bal0gPSAwOwoKICAgIHJldHVybiAoZHBbaV1bal0gPSB4K3kreit3KTsKCn0KCnZvaWQgc29sdmUoKSB7CgogICAgaW50IG4sbTsgY2luID4+IG4gPj4gbTsKCiAgICB2ZWN0b3I8cGFpcjxpbnQsaW50Pj4gYnJlYWtpbmc7CiAgICB2ZWN0b3I8dmVjdG9yPGNoYXI+PiBncmlkKG4rMSwgdmVjdG9yPGNoYXI+KG0rMSwgJy4nKSk7CiAgICB2ZWN0b3I8dmVjdG9yPGJvb2w+PiB2aXMobisxLCB2ZWN0b3I8Ym9vbD4obSsxLCAwKSk7CgogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBkcChuKzEsIHZlY3RvcjxpbnQ+KG0rMSwgLTEpKTsKCiAgICBjaW4uaWdub3JlKCk7CgogICAgZm9yIChpbnQgaT0wOyBpPG47IGkrKykgewoKICAgICAgICBzdHJpbmcgcywgcm93LCBjb2w7CiAgICAgICAgZ2V0bGluZShjaW4sIHMpOwoKICAgICAgICBzdHJpbmdzdHJlYW0gc3Mocyk7CgogICAgICAgIHNzID4+IHJvdzsKCiAgICAgICAgd2hpbGUgKHNzID4+IGNvbCkgewogICAgICAgICAgICBicmVha2luZy5wdXNoX2JhY2soe3N0b2kocm93KSwgc3RvaShjb2wpfSk7CiAgICAgICAgfQogICAgfQoKICAgIGZvciAoYXV0byBpOmJyZWFraW5nKSB7CiAgICAgICAgZ3JpZFtpLmZpcnN0XVtpLnNlY29uZF0gPSAnKic7CiAgICB9CgogICAgY291dCA8PCBQYXRocygxLDEsbixtLGdyaWQsdmlzLGRwKSA8PCAiXG5cbiI7Cgp9CgppbnQgbWFpbigpCnsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0ciksIGNvdXQudGllKG51bGxwdHIpOwoKICAgIGxsIHQ9MTsgY2luID4+IHQ7CiAgICB3aGlsZSAodC0tKSB7IHNvbHZlKCk7IH0KCiAgICByZXR1cm4gMDsKfQo=