#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MAXN = 60, MAXK = 11;
vector<int> st[MAXN];
int col[MAXN * MAXK];

vector<array<int, 2>> ans;

int n, k;

void mv(int i, int j) {
    ans.push_back({i, j});
    st[j].push_back(st[i].back());
    st[i].pop_back();
}

int block[MAXN * MAXK];

void mv_all(int i, int j) {
    while (!st[i].empty()) {
        mv(i, j);
    }
}

void move_up(int i, int b) {
    while (!st[i].empty()) {
        if (block[st[i].back()] == b) {
            mv(i, i - 1);
        } else {
            mv(i, i + 1);
        }
    }
    mv_all(i + 1, i);
    mv_all(i - 1, i);
} 

void move_down(int i, int b) {
    while (!st[i].empty()) {
        if (block[st[i].back()] == b) {
            mv(i, i - 1);
        } else {
            mv(i, i + 1);
        }
    }
    mv_all(i - 1, i);
    mv_all(i + 1, i);
}

void move_right(int i, int b) {
    move_up(i, b);
    mv_all(i + 2, i + 1);
    mv_all(i, i - 1);
    move_up(i + 1, b);
    mv_all(i - 1, i);
    if (block[st[i + 1].back()] != b && block[st[i].back()] != b) {
        mv_all(i, i - 1);
        return;
    }
    if (block[st[i + 1].back()] != b) {
        mv(i + 1, i + 2);
        mv(i + 1, i + 2);
        mv(i, i + 1);
        mv(i + 2, i + 1);
        mv(i + 1, i);
        mv(i + 2, i + 1);

        mv_all(i + 1, i + 2);
        move_up(i, b);
        mv_all(i + 2, i + 1);
        mv_all(i, i - 1);
        move_up(i + 1, b);
        mv_all(i - 1, i);
    }
    while (!st[i + 1].empty() && block[st[i + 1].back()] == b) {
        mv(i + 1, i + 2);
    }
    while (!st[i].empty() && block[st[i].back()] == b) {
        mv(i, i + 1);
        mv(i + 1, i + 2);
    }
    while (st[i].size() < k) {
        mv(i + 1, i);
    }
    mv_all(i + 2, i + 1);
    mv_all(i, i - 1);
}

void solve() {
    ans.clear();
    cin >> n >> k;
    // bottom to top

    map<int, vector<int>> rep;

    for (int i = 1; i <= n; ++i) {
        st[i].resize(k);
        for (int j = 0; j < k; ++j) {
            st[i][j] = (i - 1) * k + j;
            cin >> col[(i - 1) * k + j];
            rep[col[(i - 1) * k + j]].push_back((i - 1) * k + j);
        }
    }
    st[0].clear();
    st[n + 1].clear();
    if (k == 1) {
        cout << "TAK\n0\n";
        return;
    }
    fill(block, block + n * k, -1);
    int curb = 0;
    vector<int> lft;
    for (auto& elem : rep) {
        while (elem.second.size() >= k) {
            for (int i = 0; i < k; ++i) {
                block[elem.second.back()] = curb;
                elem.second.pop_back();
            }
            ++curb;
        }
        if (!elem.second.empty()) {
            lft.push_back(elem.first);
        }
    }
    if (lft.size() > n + 2 - curb) {
        cout << "NIE\n";
        return;
    }
    vector<int> garbage;
    vector<int> last;
    while (lft.size() > n - curb) {
        int x = lft.back();
        last.push_back(x);
        for (int t : rep[x]) {
            garbage.push_back(t);
        }
        lft.pop_back();
    }
    while (last.size() < 2) last.push_back(-1);
    for (int x : lft) {
        int cnt = 0;
        for (int i : rep[x]) {
            block[i] = curb;
            ++cnt;
        }
        while (cnt < k) {
            block[garbage.back()] = curb;
            garbage.pop_back();
            ++cnt;
        }
        ++curb;
    }

    for (int i = n + 1; i > 1; --i) {
        mv_all(i - 1, i);
    }

    for (int i = 0; i < n; ++i) {
        mv_all(2, 1);
        for (int t = 0; t < n - 1 - i; ++t) {
            move_right(t + 1, i);
        }
        int pos = n - i;
        for (int x : st[pos]) {
            if (col[x] == last[0]) {
                block[x] = 0;
            } else if (col[x] == last[1]) {
                block[x] = 1;
            } else {
                block[x] = 2;
            }
        }
        move_down(pos, 1);
        move_down(pos, 0);
        for (int t = pos - 1; t > 0; --t) {
            mv_all(t - 1, t);
        }
        for (int t = pos + 1; t > 1; --t) {
            mv_all(t - 1, t);
        }
    }
    for (int i = 2; i < n + 2; ++i) {
        while (col[st[i].back()] == last[0]) {
            for (int t = i; t > 0; --t) {
                mv(t, t - 1);
            }
        }
    }
    for (int i = 2; i < n + 2; ++i) {
        while (col[st[i].back()] == last[1]) {
            for (int t = i; t > 1; --t) {
                mv(t, t - 1);
            }
        }
    }

    assert((int)ans.size() <= 1'000'000);

    cout << "TAK\n";
    cout << ans.size() << "\n";
    for (auto elem : ans) {
        cout << elem[0] << " " << elem[1] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}