#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN=500+5,fx[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,q;
int g[MAXN][MAXN],_[MAXN][MAXN],x[MAXN*MAXN],y[MAXN*MAXN];
bool vis[MAXN][MAXN];

void Init(){
    cin>>n>>m;
    memset(g,0,sizeof g);
    for(int i=1;i<=n;i++){
        char s[MAXN];
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            g[i][j]=s[j]=='0'?1:0;
    }
    memcpy(_,g,sizeof g);
    cin>>q;
    for(int i=1;i<=q;i++) {cin>>x[i]>>y[i];x[i]++,y[i]++;}
}

bool Check(int q){
    memcpy(g,_,sizeof _);
    memset(vis,0,sizeof vis);
    for(int i=1;i<=q;i++) g[x[i]][y[i]]=0;
    queue<pair<int,int> > Q;
    for(int i=1;i<=m;i++)
        if(g[1][i]) vis[1][i]=1,Q.push(make_pair(1,i));
    while(!Q.empty()){
        int x=Q.front().first,y=Q.front().second;Q.pop();
        if(x==n) return 1;
        for(int i=0;i<4;i++){
            int nx=x+fx[i][0],ny=y+fx[i][1];
            if(!vis[nx][ny] && g[nx][ny]){
                vis[nx][ny]=1,Q.push(make_pair(nx,ny));
                if(nx==n) return 1;
            }
        }
    }
    return 0;
}

int main(){
#ifdef bhiaibogf
    freopen("in.in","r",stdin);
#endif
    int T;
    cin>>T;
    while(T--){
        Init();
        int l=1,r=q;
        if(!Check(0)) {puts("0");continue;}
        if(Check(r)) {puts("-1");continue;}
        while(l<r){
            int mid=l+((r-l)>>1);
            if(Check(mid)) l=mid+1;
            else r=mid;
        }
        cout<<l<<endl;
    }
    return 0;
}