#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>

using namespace std;

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (b) - 1; i >= (a); i--)

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;

const ll mod = 1000000007;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; for (; b; b >>= 1) { if (b & 1) res = res*a%mod; a = a*a%mod; } return res; }

int n, m;
string maz[505];
int st[505][505];
queue< pii > que;
pii c[500*505];

int d[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

int ok(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < m && maz[x][y] =='0' && st[x][y] == 0);
}

bool check() {
    memset(st, 0, sizeof(st));
    int sx = 0;
    if (sx == n - 1) return true;
    rep(sy, 0, m) {
        if (maz[sx][sy] == '1' || st[sx][sy] == 1) continue;
        while (!que.empty()) que.pop();
        que.push(mp(sx, sy));
        st[sx][sy] = 1;
        while (!que.empty()) {
            int x = que.front().first;
            int y = que.front().second;
            rep(i, 0, 4) {
                int dx = x + d[i][0];
                int dy = y + d[i][1];
                if (ok(dx, dy)) {
                    if (dx == n - 1) return true;
                    que.push(mp(dx, dy));
                    st[dx][dy] = 1;
                }
            }
            que.pop();
        }
    }
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        rep(i, 0, n) cin >> maz[i];
        int q;
        cin >> q;
        rep(i, 0, q) {
            cin >> c[i].first >> c[i].second;
        }
        int l = 0, r = q + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            rep(i, 0, mid) {
                maz[c[i].first][c[i].second] = '1';
            }
            if (check()) l = mid + 1;
            else r = mid;
            rep(i, 0, mid) {
                maz[c[i].first][c[i].second] = '0';
            }
        }
        if (r == q + 1) cout << "-1\n";
        else cout << r << endl;
    }
    return 0;
}