#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<cassert>
#define copy COPY
#define LL long long
#define LD double
#define inf 10000000000000000ll
#define mo 1000000007
using namespace std;
int st[510][510];
int x[2000100],y[2000100];
int n,m,q;
bool used[510][510];
int copx[2000100],copy[2000100];
bool zuo()
{
    memset(used,false,sizeof(used));
    int head=0,tail=0;
    for (int i=1;i<=m;i++) if (!st[1][i])
    {
        used[1][i]=true;
        copx[++head]=1;copy[head]=i;
    }
    while (head!=tail)
    {
        int px=copx[++tail],py=copy[tail];
        if ((px!=1)&&(!st[px-1][py])&&(!used[px-1][py]))
        {
            copx[++head]=px-1;copy[head]=py;
            used[px-1][py]=true;
        }
        if ((px!=n)&&(!st[px+1][py])&&(!used[px+1][py]))
        {
            copx[++head]=px+1;copy[head]=py;
            used[px+1][py]=true;
        }
        if ((py!=1)&&(!st[px][py-1])&&(!used[px][py-1]))
        {
            copx[++head]=px;copy[head]=py-1;
            used[px][py-1]=true;
        }
        if ((py!=m)&&(!st[px][py+1])&&(!used[px][py+1]))
        {
            copx[++head]=px;copy[head]=py+1;
            used[px][py+1]=true;
        }
    }
    for (int i=1;i<=m;i++) if (used[n][i]) return true;
    return false;
}
bool pend(int t)
{
    for (int i=1;i<=t;i++) st[x[i]][y[i]]=1;
    bool ans=zuo();
    for (int i=1;i<=t;i++) st[x[i]][y[i]]=0;
    return ans;
}
        
int main()
{
    int t;scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d\n",&n,&m);
        for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            char ch=getchar();
            if (ch=='1') st[i][j]=1;else st[i][j]=0;
            if (j==m) scanf("\n");
        }
        scanf("%d",&q);
        for (int i=1;i<=q;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            x[i]++;y[i]++;
        }
        if (!pend(0)) {printf("0\n");continue;}
        if (pend(q)) {printf("-1\n");continue;}
        int l=0,r=q;
        while (l+1!=r)
        {
            int mid=(l+r)>>1;
            if (pend(mid)) l=mid;else r=mid;
        }
        printf("%d\n",r);
    }
}