Ta có thể liên tục áp dụng hai quy tắc như sau để lược bỏ phần lớn các phép dò không cần thiết một cách nhanh chóng:

• Nếu tất cả mìn xung quanh một ô có số đều đã được tìm thấy, những ô chưa được dò còn lại xung quanh chắc chắn đều không có mìn.

• Nếu số lượng mìn chưa tìm thấy xung quanh một ô có số bằng với số lượng ô xung quanh chưa được dò, chắc chắn những ô này đều có mìn.

Khi hai quy tắc này không còn có thể áp dụng, ta bắt buộc phải sử dụng kết hợp các kĩ thuật suy luận cao hơn (như xét các vùng lân cận nhỏ và thử từng trường hợp), hoặc các thủ thuật xác suất/heuristic (như dò một ô ở biên để tiếp tục áp dụng hai quy tắc được cho nhiều ô hơn).

#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define lwb lower_bound
#define upb upper_bound
#define ld double
#define ins insert
#define del erase
#define ull unsigned long long
using namespace std;
const ll big=103;
const ll sml=18;
const ll inf=1e15;
const ll mod=1e9+7;
struct tr{ll fi,se,th; tr(ll _fi=0, ll _se=0, ll _th=0){fi=_fi; se=_se; th=_th;}};
struct qu{ll fi,se,th,fo,ff; qu(ll _fi=0, ll _se=0, ll _th=0, ll _fo=0, ll _ff=0){fi=_fi; se=_se; th=_th; fo=_fo; ff=_ff;}};
bool operator >(const tr &x, const tr &y){if (x.fi!=y.fi) return x.fi>y.fi; if (x.se!=y.se) return x.se>y.se; return x.th>y.th;}
bool operator <(const tr &x, const tr &y){return y>x;}
ll mxz(ll &t, ll val){if (t<val){t=val; return 1;} return 0;}
ll mnz(ll &t, ll val){if (t>val){t=val; return 1;} return 0;}
ld mxz(ld &t, ld val){if (t<val){t=val; return 1;} return 0;}
ld mnz(ld &t, ld val){if (t>val){t=val; return 1;} return 0;}
ll qpw(ll n, ll k, ll m=mod){ll p=1, t=n%m; while (k){if (k&1) p=p*t%m; t=t*t%m; k>>=1;} return p;}
ll ran(){
    ll s=0;
    for (ll i=0; i<5; ++i) s^=(ll)rand()<<(i*14ll);
    return abs(s);
}
ll ran(ll l, ll r){
    return ran()%(r-l+1)+l;
}
ld ranl(ld l, ld r){
    return ran(l*1000000.0L,r*1000000.0L)*0.000001L;
}
ll sqr(ll x){
    return x*x;
}
namespace solution{
    ll n,m,k;
    ll bom[big][big];
    ll cbom[big][big];
    ll fbom[big][big];
    ll vis[big][big];
    ll cvis[big][big];
    ll mvis[big][big];
    ll flag=0;
    ll x,y;
    vector<ii> col;
    void init(ll _n, ll _m, ll _k){
        n=_n; m=_m; k=_k;
        memset(bom,0,sizeof(bom));
        memset(cbom,0,sizeof(cbom));
        memset(fbom,0,sizeof(fbom));
        memset(vis,0,sizeof(vis));
        memset(cvis,0,sizeof(cvis));
        for (ll i=1; i<=n; ++i) for (ll j=1; j<=m; ++j) mvis[i][j]=(min(n,i+1)-max(1ll,i-1)+1)*(min(m,j+1)-max(1ll,j-1)+1)-1;
        col.clear();
        for (ll i=1; i<=n; ++i) for (ll j=1; j<=m; ++j) col.eb(i,j);
        sort(col.begin(),col.end());
        flag=0;
    }
    ll check(ll x, ll y){
        for (ll i=max(1ll,x-1); i<=min(n,x+1); ++i) for (ll j=max(1ll,y-1); j<=min(m,y+1); ++j) if (!bom[i][j] && vis[i][j] && (x!=i || y!=j)){
            ll cur=bom[i-1][j-1]+bom[i-1][j]+bom[i-1][j+1]+bom[i][j-1]+bom[i][j+1]+bom[i+1][j-1]+bom[i+1][j]+bom[i+1][j+1];
            if (cur+mvis[i][j]-cvis[i][j]-1<cbom[i][j] || cur>cbom[i][j]) return 0;
        }
        return 1;
    }
    void update(){
        for (ll i=max(1ll,x-1); i<=min(n,x+1); ++i) for (ll j=max(1ll,y-1); j<=min(m,y+1); ++j){
            fbom[i][j]=cbom[i][j];
            for (ll u=max(1ll,i-1); u<=min(n,i+1); ++u) for (ll v=max(1ll,j-1); v<=min(m,j+1); ++v) fbom[i][j]-=bom[u][v];
            cvis[i][j]=vis[i-1][j-1]+vis[i-1][j]+vis[i-1][j+1]+vis[i][j-1]+vis[i][j+1]+vis[i+1][j-1]+vis[i+1][j]+vis[i+1][j+1];
        }
    }
    ii helper(){
        if (flag==0){
            do {
                x=col.back().fi; y=col.back().se;
                col.pop_back();
            } while (vis[x][y]);
            return ii(x,y);
        }
        if (1){
            for (ll i=1; i<=n; ++i) for (ll j=1; j<=m; ++j) if (vis[i][j]==0 && cvis[i][j]>0){
                ll ok=0;
                vis[i][j]=1;
                bom[i][j]=1; if (check(i,j)) ok|=2;
                bom[i][j]=0; if (check(i,j)) ok|=1;
                vis[i][j]=0; 
                x=i; y=j;
                if (ok==1) return ii(x,y);
                if (ok==2){
                    vis[x][y]=bom[x][y]=1;
                    update();
                    return ii(-1,-1);
                }
            }
        }
        if (1){
            for (ll i=1; i<=n; ++i) for (ll j=1; j<=m; ++j) if (fbom[i][j]>=1 && cvis[i][j]<mvis[i][j]){
                for (ll u=max(1ll,i-1); u<=min(n,i+1); ++u) for (ll v=max(1ll,j-1); v<=min(m,j+1); ++v){
                    if (fbom[u][v]>=1 && fbom[u][v]<=fbom[i][j]){
                        ll fvis=mvis[i][j]-cvis[i][j];
                        for (ll I=max(1ll,u-1); I<=min(n,u+1); ++I) for (ll J=max(1ll,v-1); J<=min(m,v+1); ++J) if (!vis[I][J]){
                            if (I<i-1 || I>i+1 || J<j-1 || J>j+1) goto amongus;
                            --fvis;
                        }
                        if (fbom[i][j]-fbom[u][v]==0){
                            for (ll I=max(1ll,i-1); I<=min(n,i+1); ++I) for (ll J=max(1ll,j-1); J<=min(m,j+1); ++J) if (!vis[I][J]){
                                if (u-1<=I && I<=u+1 && v-1<=J && J<=v+1) continue;
                                x=I; y=J;
                                return ii(x,y);
                            }
                        }
                        if (fbom[i][j]-fbom[u][v]==fvis){
                            for (ll I=max(1ll,i-1); I<=min(n,i+1); ++I) for (ll J=max(1ll,j-1); J<=min(m,j+1); ++J) if (!vis[I][J]){
                                if (u-1<=I && I<=u+1 && v-1<=J && J<=v+1) continue;
                                x=I; y=J;
                                vis[x][y]=bom[x][y]=1;
                                update();
                                return ii(-1,-1);
                            }
                        }
                        amongus:;
                    }
                }
            }
        }
        ll cvistotal=0;
        for (ll i=1; i<=n; ++i) for (ll j=1; j<=m; ++j) cvistotal+=vis[i][j];
        if (cvistotal==n*m) return ii(0,0);
        flag=0; return ii(-1,-1);
    }
    ii move(){
        ii ans;
        do ans=helper(); while (ans.fi==-1);
        return ans;
    }
    void get(ll ans){
        vis[x][y]=1;
        if (ans==-1) bom[x][y]=1; else cbom[x][y]=ans;
        update();
        flag=1;
    }
    vector<ii> ans(){
        vector<ii> tmp;
        for (ll i=1; i<=n; ++i) for (ll j=1; j<=m; ++j) if (bom[i][j]) tmp.eb(i,j);
        return tmp;
    }
};
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll tst; cin>>tst;
    for (; tst; --tst){
        ll n,m,k; cin>>n>>m>>k;
        solution::init(n,m,k);
        do {
            ii t=solution::move();
            cout<<t.fi<<" "<<t.se<<endl;
            if (t.fi==0 && t.se==0){
                vector<ii> sol=solution::ans();
                for (const ii &t: sol) cout<<t.fi<<" "<<t.se<<"\n";
                cout.flush();
                break;
            }
            ll ans; cin>>ans;
            solution::get(ans);
        } while (1);
    }
    return 0;
}