#include <cmath>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <cstdlib>
#include <fstream>
#include <cmath>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const int maxn=508;
const int Mod=1e9+7;

int T,n,m,q;
int s[maxn][maxn];
char mp[maxn][maxn];
int curmp[maxn][maxn];
bool vis[maxn][maxn];

int block[maxn*maxn][2];
int dir[4][2]={0,1,0,-1,-1,0,1,0};

int maxblock;

struct Node
{
    int x,y;
    Node(){}
    Node(int tx,int ty){x=tx; y=ty;}
};

inline bool in(int x,int y)
{
    if (x>=0 && x<n && y>=0 && y<m) return true;
    return false;
}

bool bfs(int sx,int sy)
{
    queue<Node> qu;
    qu.push(Node(sx,sy));
    Node t;
    int dx,dy;
    mem(vis,0);
    vis[sx][sy]=1;
    while(!qu.empty()){
        t=qu.front();
        qu.pop();
        for (int i=0;i<4;i++){
            dx=t.x+dir[i][0];
            dy=t.y+dir[i][1];
            if (in(dx,dy) && curmp[dx][dy]==0 && !vis[dx][dy]){
                if (dx==0) return true;
                vis[dx][dy]=1;
                qu.push(Node(dx,dy));
            }
        }
    }
    return false;
}

bool run(int pos)
{
//    if (pos>maxblock){    
//        memcpy(curmp,s,sizeof(s));
//        for (int i=maxblock+1;i<=pos;i++) curmp[block[i][0]][block[i][1]]=1;
//        maxblock=pos;
//    }else if (pos<maxblock){
//        maxblock=pos;
//        memcpy(curmp,s,sizeof(s));
//        for (int i=1;i<=pos;i++) curmp[block[i][0]][block[i][1]]=1;
//    }
    memcpy(curmp,s,sizeof(s));
    for (int i=1;i<=pos;i++) curmp[block[i][0]][block[i][1]]=1;    
    for (int i=0;i<m;i++){
        if (curmp[n-1][i]==0 && bfs(n-1,i)) return true;
    }
    return false;
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
     //   freopen("out.txt","w",stdout);
    #endif
    
    scanf("%d",&T);
    while(T--){
        maxblock=-1;
        
        scanf("%d %d",&n,&m);
        
        for (int i=0;i<n;i++) 
        {
            scanf("%s",mp[i]);        
            for (int j=0;j<m;j++) 
            {
                if (mp[i][j]=='0')  s[i][j]=0;
                else s[i][j]=1;
            }
        }
        scanf("%d",&q);
        mem(block,0);
        for (int i=1;i<=q;i++) scanf("%d %d",&block[i][0],&block[i][1]);
        int l=0,r=q;
        bool ok;
        while(l<r){
            int mid=(l+r)>>1;
        //    cout<<mid<<" "<<run(mid)<<" "<<l<<" "<<r<<endl;
            if (ok=run(mid)) l=mid+1;
            else r=mid;
        }
        int a=l,b=r,c=(l+r)>>1;
        if (run(a) && run(b) && run(c)) printf("-1\n");
        else printf("%d\n",min(min(a,b),c));
        //cout<<l<<" "<<r<<endl;
    //    printf("%d\n",!ok? l:-1);
    }
    return 0;
}