#include <cstdio>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define getmid(l,r) ((l) + ((r) - (l)) / 2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define MP(a,b) make_pair(a,b)
#define PB push_back

typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int INF = (1 << 30) - 1;
const int MAXN = 100010;
const ll mod = 1e9 + 7;

int T,N,M,Q;
char g[510][510],tg[510][510];
int qq[510 * 510][2];
bool vis[510][510];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

bool Bfs(){
    memset(vis,false,sizeof(vis));
    queue<pii > Q;
    while(!Q.empty()) Q.pop();
    for(int i = 1; i <= M; ++i) if(tg[1][i] == '0') Q.push(MP(1,i)),vis[1][i] = 1;
    while(!Q.empty()){
        pii x = Q.front(); Q.pop();
        if(x.first == N) return true;
        for(int k = 0; k < 4; ++k){
            int ti = x.first + dir[k][0];
            int tj = x.second + dir[k][1];
            if(ti < 1 || ti > N || tj < 1 || tj > M || tg[ti][tj] == '1') continue;
            if(vis[ti][tj]) continue;
            vis[ti][tj] = 1;
            Q.push(MP(ti,tj));
        }
    }
    return false;
}

bool Check(int v){
    memcpy(tg,g,sizeof(g));
    for(int i = 1; i <= v; ++i){
        tg[qq[i][0]][qq[i][1]] = '1';
    }
    return Bfs();
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        for(int i = 1; i <= N; ++i){
            scanf("%s",g[i] + 1);
        }
        scanf("%d",&Q);
        for(int i = 1; i <= Q; ++i){
            scanf("%d%d",&qq[i][0],&qq[i][1]);
            qq[i][0]++;
            qq[i][1]++;
        }
        int l = 0,r = Q + 1;
        while(l < r){
            int mid = getmid(l,r);
            if(Check(mid)) l = mid + 1;
            else r = mid;
        }
        if(l > Q){
            printf("-1\n");
        }
        else{
            printf("%d\n",l);
        }
    }
    return 0;
}