#include<bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double
#define mod 998244353ll
#define INF 1000000000000000000ll

bool pisac = true;

int T, k;

int tab[30][30];
int id[30][30];
int zloto[30];
int skaly[30];
int farmerzy_na_linii[30];
int ile_pojazdow[30];

int l_farmer, l_tank;
int suma_zlota, suma_skal;
int n;
bool wolna_droga_dla_tankow;
int ile_farmerow, ile_tankow;
int ile_w_banku;
int do_zniesienia;

struct algo {
    struct samochodzik {
        int r, c;
        int plecak;
        bool czy_tank;
        bool czy_tank_skonczyl;
        bool visited;
        int nr;

        samochodzik( bool tank, int ID ) {
            r = c = 0;
            plecak = 0;
            czy_tank = tank;
            czy_tank_skonczyl = 0;
            visited = 0;
            nr = ID;
            id[r][c] = nr;
            if( pisac ) {
                if( tank ) cout << "R TANK\n";
                else cout << "R FARMER\n";
            }
        }

        pair<int, int> nastepne_po_przekotnej() {
            if( r==0 && c>0 ) return {r, c-1};
            if( r<=c ) return {r-1, c};
            return {r, c+1};
        }

        pair<int, int> poprzednie_po_przekotnej() {
            if( c==0 ) return {r+1, c};
            if( r>=c ) return {r, c-1};
            return {r+1, c};
        }

        pair<int, int> nastepne_pole() {
            if( !czy_tank ) {
                if( c==0 && r<l_farmer ) return {r+1, c};
                return nastepne_po_przekotnej();
            } else {
                if( czy_tank_skonczyl ) {
                    //cout <<"asfda" << endl;
                    if( c==0 && r+1<n ) return {r+1, c};
                    return nastepne_po_przekotnej();
                }
                if( (c!=0 || r+1>=l_tank) && max(r, c)%2==1 ) { //tak jak farmer
                    if( r == 0 ) return {r, c+1};
                    else return nastepne_po_przekotnej();
                } else if( c!=0 ) {
                    return poprzednie_po_przekotnej();
                } else {
                    return {r+1, c};
                }
            }
        }

        void rusz() {
            pair<int, int> p = nastepne_pole();
            id[r][c] = -1;
            if( pisac ) cout << "M " << r << " " << c << " " << p.first << " " << p.second << "\n";
            if( !czy_tank ) {
                if( c ) farmerzy_na_linii[max(r, c)]--;
                if( p.second ) farmerzy_na_linii[max(p.first, p.second)]++;
            }
            r = p.first;
            c = p.second;
            id[r][c] = nr;
            if( r==0 && c==n-1 ) czy_tank_skonczyl = true;
        }

        void kop() {
            if( !czy_tank ) {
                if( tab[r][c] > 0 ) {
                    int pom = min( 10, tab[r][c] );
                    plecak += pom;
                    tab[r][c] -= pom;
                    if( pom && tab[r][c] == 0 ) zloto[max(r,c)]--;
                    suma_zlota -= pom;
                }
                if( r==0 && c==0 ) {
                    ile_w_banku += plecak;
                    do_zniesienia -= plecak;
                    plecak = 0;
                }
            } else {
                if( tab[r][c] < 0 ) {
                    int pom = min( 10, -tab[r][c] );
                    tab[r][c] += pom;
                    if( pom && tab[r][c] == 0 ) skaly[max(r,c)]--;
                    suma_skal -= pom;
                }
            }
        }
    };
    vector<samochodzik> v;

    algo() {
        cin >> n;
        l_farmer=1, l_tank=1;
        suma_zlota = 0, suma_skal = 0;
        ile_farmerow = ile_tankow = 0;
        wolna_droga_dla_tankow = false;
        ile_w_banku = 200;
        do_zniesienia = 0;
        for( int i=0; i<n; i++ ) {
            zloto[i] = skaly[i] = 0;
            farmerzy_na_linii[i] = 0;
            ile_pojazdow[i] = 0;
        }
        for( int i=0; i<n; i++ ) {
            for( int j=0; j<n; j++ ) {
                cin >> tab[i][j];
                if( tab[i][j] > 0 ) {
                    suma_zlota += tab[i][j];
                    do_zniesienia += tab[i][j];
                    zloto[ max(i, j) ]++;
                }
                else {
                    suma_skal -= tab[i][j];
                    skaly[ max(i, j) ]++;
                }
                id[i][j] = -1;
            }
        }

        if( suma_skal == 0 ) {
            bez_tankow();
            return;
        }
        z_tankami();

        /*v.push_back( {false, v.size()} );
        for( int i=0; i<30; i++ ) {
            wypisz();
            v[0].rusz();
            char c;
            cin >> c;
        }*/
        /*for( int i=0; i<30; i++ ) {
            if( rand()%2 )
            v.push_back( {rand()%2, v.size()} );
            for( int j=0; j<(int)v.size(); j++ ) {
                dfs( j );
            }
            for( int j=0; j<(int)v.size(); j++ ) {
                v[j].visited = false;
            }
            char c;
            cin >> c;
            wypisz();
        }*/
    }

    void z_tankami() {
        ile_w_banku -= 100;
        v.push_back( {true, v.size()} );
        ile_tankow++;
        v[0].rusz();
        if( pisac ) cout << "=\n";
        ile_w_banku -= 100;
        v.push_back( {false, v.size()} );
        ile_farmerow++;
        if( pisac ) cout << "=\n";
        while( do_zniesienia ) {
            if( ile_w_banku >= 100 && id[0][0] == -1 && ile_pojazdow[l_farmer] <= l_farmer*4-2 && ile_farmerow+ile_tankow <= (n-1)*4-2 ) {
                ile_w_banku -= 100;
                if( ile_tankow*suma_zlota < ile_farmerow*suma_skal && ile_tankow < n ) {
                    v.push_back( {true, v.size()} );
                    ile_tankow++;
                } else {
                    v.push_back( {false, v.size() } );
                    ile_farmerow++;
                }
            }

            for( int i=0; i<v.size(); i++ ) {
                if( !v[i].czy_tank && tab[v[i].r][v[i].c] <= 0 ) {
                    dfs( i );
                }
                if( v[i].czy_tank && tab[v[i].r][v[i].c] >= 0 ) {
                    if( suma_skal > 0 || max(v[i].r, v[i].c)+1 < n)
                        dfs( i );
                }
            }
            for( int i=0; i<n; i++ ) {
                ile_pojazdow[i] = 0;
            }
            for( int i=0; i<v.size(); i++ ) {
                v[i].visited = false;
                v[i].kop();
                ile_pojazdow[ max(v[i].r, v[i].c) ]++;
            }
            for( int i=1; i<n; i++ ) {
                ile_pojazdow[i] += ile_pojazdow[i-1];
            }
            if( tab[1][1] <= 0 && zloto[ l_farmer ] <= farmerzy_na_linii[ l_farmer ] && l_farmer+1 < n ) {
                if( ile_pojazdow[l_farmer+1]-ile_farmerow == 0 ) {
                    l_farmer++;
                } else if( l_farmer+2 == n && suma_skal == 0 ) {
					l_farmer++;
				}
            }
            if( l_farmer+1 >= n ) wolna_droga_dla_tankow = true;
            if( skaly[l_tank] == 0 && l_tank+1 < n ) l_tank++;
            if( pisac ) cout << "=\n";
			//char c;
            //cin >> c;
            //wypisz();
            //cout << ile_w_banku << " " << do_zniesienia << " " << suma_skal << endl;
        }
        if( pisac ) cout << "===\n";
    }

    void bez_tankow() {
        while( do_zniesienia ) {
            if( ile_w_banku >= 100 && id[0][0] == -1 && ile_farmerow <= l_farmer*4-2 ) {
                ile_w_banku -= 100;
                v.push_back( {false, v.size()} );
                ile_farmerow++;
            }

            for( int i=0; i<v.size(); i++ ) {
                if( tab[v[i].r][v[i].c] <= 0 ) {
                    dfs( i );
                }
            }
            for( int i=0; i<v.size(); i++ ) {
                v[i].visited = false;
                v[i].kop();
            }
            if( zloto[ l_farmer ] <= farmerzy_na_linii[ l_farmer ] && l_farmer+1 < n ) l_farmer++;
            if( pisac ) cout << "=\n";
            //char c;
            //cin >> c;
            //wypisz();
            //cout << zloto[1] << " " << do_zniesienia << endl;
        }
        if( pisac ) cout << "===\n";
    }

    bool dfs( int nr ) {
        if( v[nr].visited ) return false;
        v[nr].visited = true;
        pair<int, int> p = v[nr].nastepne_pole();
        if( !v[nr].czy_tank && tab[p.first][p.second] < 0 ) return false;
        if( v[nr].czy_tank && v[nr].r == 0 && v[nr].c == n-1 && !wolna_droga_dla_tankow ) return false;
        int x = id[p.first][p.second];
        if( x==-1 || dfs( x ) ) {
            v[nr].rusz();
            return true;
        }
        return false;
    }

    void wypisz() {
        for( int i=0; i<n; i++ ) {
            for( int j=0; j<n; j++ ) {
                if( id[i][j] != -1 ) {
                    if( v[ id[i][j] ].czy_tank ) cout << 'T';
                    else cout << 'F';
                } else {
                    cout << '.';
                }
            }
            cout << "\n";
        }
        cout << "\n";
        for( int i=0; i<n; i++ ) {
            for( int j=0; j<n; j++ ) {
                cout << tab[i][j] << " ";
            }
            cout << "\n";
        }
    }
};

int32_t main() {
    ios_base::sync_with_stdio( 0 );
    cin.tie( 0 );

    cin >> T >> k;

    while( T-- ) {
        algo p;
    }

    return 0;
}/*


1 1
4
0 200 1 1
10 1000 0 0
0 1000 0 0
1 1 1 1

1 12
4
0 -8 -512 0
-16 -1 -128 0
8 -2 -512 0
0 0 0 0

1 12
4
0 -8 -512 0
-16 300 -128 0
8 -2 -512 0
0 0 0 0

1 1
3
0 0 0
0 0 0
8 0 0
*/