#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
const int maxn=510;
int n,m,q;
char a[maxn][maxn];
char backup[maxn][maxn];
int color[maxn][maxn];
int le[]={-1,0,1,0};
int ri[]={0,1,0,-1};
struct pos{
    int x,y;
    pos(int x=0,int y=0):x(x),y(y) {}
}p[maxn*maxn];
inline bool in(int x,int y){
    return x>=0&&y>=0&&x<=n&&y<m;
}
bool bfs(int cur){
    memcpy(a,backup,sizeof(backup));
    for(int i=0;i<=cur;++i) a[p[i].x][p[i].y]='1';
    memset(color, 0, sizeof(color));
    queue<pos> qu;
    for(int i=0;i<m;++i) qu.push(pos(0, i));
    while(!qu.empty()){
        pos t=qu.front(); qu.pop();
        if(a[t.x][t.y]=='1') continue;
        for(int i=0;i<4;++i){
            pos ne; ne.x=t.x+le[i]; ne.y=t.y+ri[i];
            if(t.x==n) return true;
            if(!in(ne.x,ne.y)) continue;
            if(color[ne.x][ne.y]) continue;
            if(a[ne.x][ne.y]=='1') continue;
            qu.push(ne);color[ne.x][ne.y]=1;
        }
    }
//    for(int i=0;i<m;++i) if(color[n][i]) return true;
    return false;
}
int main(){
    //freopen("a.txt", "r", stdin);
    int T; scanf("%d\n", &T);
    while(T--){
        scanf("%d%d", &n,&m);
        for(int i=0;i<n;++i) scanf("%s", backup[i]);
        scanf("%d", &q);
        for(int i=0;i<q;++i) scanf("%d%d", &p[i].x, &p[i].y);
        int l=-1,r=q-1;
        int mid;
        while(l!=r&&(r-l>=2)){
            mid=(l+r)/2;
            if(bfs(mid)) l=mid;
            else r=mid;
        }
        if(!bfs(l)) printf("%d\n", l+1);
        else if(!bfs(r)) printf("%d\n", r+1);
        else printf("-1\n");
    }
    return 0;
}