//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef XOX
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void solve(){
    int n, k; cin >> n >> k;
    vector a(n+2, vector<char>(n+2, '.'));
    vector<vector<T>>pos(3);
    auto ch = [&](char c){
        if (c == 'x') return 1;
        if (c == 'o') return 2;
        return 0;
    };
    auto rev = [&](int x){
        if (x == 1) return 'x';
        if (x == 2) return 'o';
        return '.';
    };
    vector<int>X = {1, 0, 1, -1};
    vector<int>Y = {0, 1, 1, 1};
    auto check = [&](vector<vector<char>>b){
        for (int i = 1; i<=n; i++){
            for (int j = 1; j<=n; j++){
                if (b[i][j] == '.') continue;
                for (int ck = 0; ck < 4; ck++){
                    T pos = {i, j};
                    bool ok = 1;
                    int tmp = k;
                    while (tmp--){
                        if (min(pos.first, pos.second) < 1 || max(pos.first, pos.second) > n){
                            ok = 0;
                            break;
                        }
                        ok &= (b[pos.first][pos.second] == b[i][j]);
                        pos = {pos.first+X[ck], pos.second + Y[ck]};
                    }
                    if (ok) return true;
                }
            }
        }
        return false;
    };
    vector<int>ile(3);
    for (int i = 1; i<=n; i++){
        for (int j = 1; j<=n; j++){
            cin >> a[i][j];
            ile[ch(a[i][j])]++;
            pos[ch(a[i][j])].emplace_back(i, j);
        }
    }
    if (abs(ile[1]-ile[2]) > 1){
        cout << "NIE\n";
        return;
    }
    vector<T>where;
    vector<int>curr(3);
    int tmp = 0;
    if (!check(a)){
        if (ile[1]+ile[2] == n*n) {
            //remis
            debug(2137);
            goto OK;
        } else {
            cout << "NIE\n";
            return;
        }
    }
    for (int i = 1; i<=n; i++){
        for (int j = 1; j<=n; j++){
            if (a[i][j] != '.'){
                char now = a[i][j];
                a[i][j] = '.';
                if (!check(a)){
                    where.emplace_back(i, j);
                    curr[ch(now)]++;
                } else {
                    tmp++;
                }
                a[i][j] = now;
            }
        }
    }
    
    debug(where, curr);
    debug(tmp, ile[1]+ile[2]);
    if ((int)where.empty() || (tmp == 0) || (curr[1] > 0 && curr[2] > 0)){
        cout << "NIE\n";
        return;
    }
    OK:;
    T last = {1, 1};
    if (where.empty()){
        for (int i = 1; i<=n; i++){
            for (int j =1; j<=n; j++){
                if (ile[ch(a[i][j])] == max(ile[1], ile[2])){
                    last = {i, j};
                    break;
                }
            }
        }
    } else last = where[0];
    int type = ch(a[last.first][last.second]);
    if (ile[type] < max(ile[1], ile[2])){
        cout << "NIE\n";
        return;
    }
    cout << "TAK\n";
    debug(last);
    vector vis(n+1, vector<bool>(n+1));
    vis[last.first][last.second] = 1;
    vector<T>ret = {last};
    debug(pos[1], pos[2]);
    while ((int)ret.size() < ile[1]+ile[2]){
        type = (type == 1 ? 2 : 1);
        auto now = pos[type].back();
        debug(now);
        if (vis[now.first][now.second]){
            pos[type].pop_back();
            now = pos[type].back();
        }
        vis[now.first][now.second] = 1;
        pos[type].pop_back();
        ret.emplace_back(now);
    } 
    reverse(ret.begin(), ret.end());
    for (auto [a, b]: ret) {
        cout << a << " " << b << "\n";
    }
}

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

    int t = 1;
    cin >> t;
    while (t--) solve();

    return 0;
}