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

char buff[1000];

int dx[] = {0, 0, 1,-1, 1, 1,-1,-1};
int dy[] = {1,-1, 0, 0, 1,-1, 1,-1};

bool check(vector<string>& vv, int h, int w){
    queue<int> q;
    vector<bool> visit( h*w , false);
    for(int i=0; i<w; i++){
        if(vv[0][i] == '0'){
            q.push(0*w + i);
            visit[0*w + i] = true;
        }
    }
    
    while(q.size()){
        int p = q.front();
        q.pop();

        int y = p/w;
        int x = p%w;

        if(y == h-1){
            return true;
        }

        for(int k__=0; k__<4; k__++){
            int new_x = x + dx[k__];
            int new_y = y + dy[k__];
            if(new_x < 0 || new_x >= w || new_y < 0 || new_y >= h) continue;
            if(vv[new_y][new_x] == '1') continue;
            int next = new_y*w + new_x;
            if(visit[next] ) continue;
            visit[next] = true;
            q.push(next);
        }
    }
    return false;
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n,m;
        scanf("%d%d", &n, &m);
        vector<string> v(n);
        for(int i=0; i<n; i++){
            scanf("%s", buff);
            v[i] = buff;
        }
        int q;
        scanf("%d", &q);
        vector<int> r(q),c(q);
        for(int i=0; i<q; i++){
            scanf("%d%d", &r[i], &c[i]);
        }

        {
            bool ok = check(v, n,m);
            if(ok == false){
                puts("0");
                continue;
            }
        }

        int lb = 0;
        int ub = q+1;
        while(ub-lb>1){
            int mid = (lb+ub)/2;

            vector<string> vv = v;
            for(int i=0; i<mid; i++){
                vv[r[i]][c[i]] = '1';
            }

            bool ok = check(vv, n,m);
            
            (ok? lb : ub) = mid;
        }

        if(lb==q){
            vector<string> vv = v;
            for(int i=0; i<lb; i++){
                vv[r[i]][c[i]] = '1';
            }

            bool ok = check(vv, n,m);
            if(ok){
                puts("-1");
            }else{
                printf("%d\n", lb+1);
            }
        }else{
            printf("%d\n", lb+1);
        }
    }
    return 0;
}