#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#define N 510
using namespace std;
struct node{int fa1,fa2,up,down;}h[N][N];
int n,m,b[N][N],ql,q[N*N][2],step[4][2],ans;
char s[N];
bool v[N][N];
void find(int x,int y,int &fa1,int &fa2)
{
    if(x!=h[x][y].fa1 || y!=h[x][y].fa2) 
        find(h[x][y].fa1,h[x][y].fa2,fa1,fa2);
    else fa1=h[x][y].fa1,fa2=h[x][y].fa2;
    h[x][y].fa1=fa1;
    h[x][y].fa2=fa2;
}
void comb(int fx1,int fx2,int fy1,int fy2)
{
    h[fx1][fx2].fa1=fy1;
    h[fx1][fx2].fa2=fy2;
    h[fy1][fy2].up|=h[fx1][fx2].up;
    h[fy1][fy2].down|=h[fx1][fx2].down;
}
void dfs(int x,int y)
{
    v[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int xx=x+step[i][0],yy=y+step[i][1];
        if(xx>n || xx<1 || yy>m || yy<1) continue;
        if(v[xx][yy]==0 && b[xx][yy]==0) 
        {
            dfs(xx,yy);    
            int fx1,fx2,fy1,fy2;
            find(x,y,fx1,fx2);
            find(xx,yy,fy1,fy2);
            if(fx1!=fy1 || fx2!=fy2) comb(fx1,fx2,fy1,fy2);
        }
    }
}
int main()
{
    step[0][0]=1;step[0][1]=0;
    step[1][0]=-1;step[1][1]=0;
    step[2][0]=0;step[2][1]=1;
    step[3][0]=0;step[3][1]=-1;
    int z;
    scanf("%d",&z);
    while(z--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s+1);
            for(int j=1;j<=m;j++) b[i][j]=s[j]-'0';
        }
        scanf("%d",&ql);
        for(int i=1;i<=ql;i++) 
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x++;y++;
            b[x][y]=1;
            q[i][0]=x;
            q[i][1]=y;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                v[i][j]=0;
                h[i][j].fa1=i;
                h[i][j].fa2=j;
                h[i][j].up=h[i][j].down=0;
                if(i==1) h[i][j].up=1;
                if(i==n) h[i][j].down=1;
            }
        bool bo=0;
        for(int i=1;i<=n;i++)
        {
            if(bo) break;
            for(int j=1;j<=m;j++)
                if(v[i][j]==0 && b[i][j]==0) 
                {
                    dfs(i,j);
                    int fx1,fx2;
                    find(i,j,fx1,fx2);
                    if(h[fx1][fx2].up && h[fx1][fx2].down) {bo=1;break;}
                }
        }
        if(bo) {printf("-1\n");continue;}
        ans=0;
        for(int i=ql;i>=1;i--)
        {
            int fx1,fx2,fy1,fy2;
            int x=q[i][0],y=q[i][1];
            for(int j=0;j<4;j++)
            {
                int xx=x+step[j][0],yy=y+step[j][1];
                if(xx>n || xx<1 || yy>m || yy<1) continue;
                if(b[xx][yy]) continue;
                find(x,y,fx1,fx2);
                find(xx,yy,fy1,fy2);
                if(fx1!=fy1 || fx2!=fy2) comb(fx1,fx2,fy1,fy2);
            }
            b[x][y]=0;
            find(x,y,fx1,fx2);
            if(h[fx1][fx2].up && h[fx1][fx2].down) {ans=i;break;}
        }
        printf("%d\n",ans);
    }
    return 0;
}