#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 505;

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

char g[N][N];

struct node
{
    int x, y;
}a[N*N];

int find(int x)
{
    int res, t;
    for (res=x; dset[res]!=res; res=dset[res])
        continue;
    while (x != res) {
        t = dset[x];
        dset[x] = res;
        x = t;
    }
    return res;
}

void merge(int x, int y)
{
    int fx=find(x), fy=find(y);
    dset[fx] = fy;
}

void solve()
{
    memset(g, 1, sizeof(g));
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i=0; i<(n+1)*(m+1); ++i) {
        dset[i] = i;
    }
    for (int i=m+1; i<=m+m; ++i) {
        merge(i, 0);
    }
    for (int i=n*m+1; i<=n*m+m; ++i) {
        merge(i, 1);
    }
    for (int i=1; i<=n; ++i) {
        scanf("%s", g[i]+1);
        for (int j=1; j<=m; ++j) {
            g[i][j] -= '0';
        }
        g[i][m+1] = 1;
    }
    int q;
    scanf("%d", &q);
    for (int i=1; i<=q; ++i) {
        scanf("%d%d", &a[i].x, &a[i].y);
        ++a[i].x;
        ++a[i].y;
        g[a[i].x][a[i].y] = 1;
    }
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            for (int k=0; k<4; ++k) {
                int x=i+d[k][0], y=j+d[k][1];
                if (g[i][j] || g[x][y]) {
                    continue;
                }
                merge(i*m+j, x*m+y);
            }
        }
    }
    if (find(0) == find(1)) {
        printf("-1\n");
        return;
    }
    for (int qi=q; qi>0; --qi) {
        int i=a[qi].x, j=a[qi].y;
        for (int k=0; k<4; ++k) {
            int x=i+d[k][0], y=j+d[k][1];
            g[i][j] = 0;
            if (g[x][y]) {
                continue;
            }
            merge(i*m+j, x*m+y);
        }
        if (find(0) == find(1)) {
            printf("%d\n", qi);
            return;
        }
    }
    printf("0\n");
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i=0; i<n; ++i) {
        solve();
    }
    return 0;
}