#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


constexpr int MAX = 60;

int N, K;
int A[MAX][MAX];

int L[MAX];
int B[MAX][MAX];

vector<pair<int, int>> ans;
void oper(int i, int j) {
  assert(0 <= i); assert(i <= N + 1);
  assert(0 <= j); assert(j <= N + 1);
  assert(abs(j - i) == 1);
  if (L[i] > 0 && L[j] < K) {
    ans.emplace_back(i, j);
    B[j][L[j]++] = B[i][--L[i]];
  }
}
void out() {
#ifdef LOCAL
  cerr << string(8, '-') << endl;
  for (int i = 0; i <= N + 1; ++i) {
    cerr << i << ": ";
    for (int k = 0; k < L[i]; ++k) {
      cerr << B[i][k] << " ";
    }
    cerr << endl;
  }
  cerr << string(8, '-') << endl;
#endif
}

void judge() {
  vector<vector<int>> a(N + 2);
  for (int i = 1; i <= N; ++i) {
    for (int k = 0; k < K; ++k) {
      a[i].push_back(A[i][k]);
    }
  }
  for (const auto &op : ans) {
    const int i = op.second;
    const int j = op.first;
// cerr<<"judge "<<a<<"; "<<i<<" -> "<<j<<endl;
    assert(0 <= i); assert(i <= N + 1);
    assert(0 <= j); assert(j <= N + 1);
    assert(abs(j - i) == 1);
    assert((int)a[i].size() > 0);
    assert((int)a[j].size() < K);
    a[j].push_back(a[i].back());
    a[i].pop_back();
  }
  for (int i = 0; i <= N + 1; ++i) if (!a[i].empty()) {
    for (const int val : a[i]) {
      assert(a[i][0] == val);
    }
  }
}

void move(int ti, int tk, int si, int val) {
#ifdef LOCAL
cerr<<"move ("<<ti<<", "<<tk<<") "<<si<<" "<<val<<endl;
#endif
out();
  if (ti == si) {
    int sk = -1;
    for (int k = tk; k < L[ti]; ++k) {
      if (B[ti][k] == val) {
        sk = k;
        break;
      }
    }
    assert(~sk);
    if (tk == sk) {
      return;
    }
    for (int i = N; i > ti; --i) {
      for (int k = 0; k < K; ++k) oper(i, i + 1);
    }
// cerr<<"sk = "<<sk<<endl;
    assert(L[ti] == K);
    assert(L[ti + 1] == 0);
    assert(L[ti + 2] == 0);
    for (; L[ti] > sk; ) {
      oper(ti, ti + 1);
      oper(ti + 1, ti + 2);
    }
    for (; L[ti] > tk; ) {
      oper(ti, ti + 1);
    }
    oper(ti + 2, ti + 1);
    oper(ti + 1, ti);
    // ue tsumeru
    for (int i = ti + 1; i <= ti + 2; ++i) {
      for (int j = i; j > ti; --j) {
        for (int k = 0; k < K; ++k) oper(j, j - 1);
      }
    }
  } else {
    for (int i = ti + 1; i <= ti + 2; ++i) {
      if (si == i) {
        for (int k = 0; k < K; ++k) oper(i, i + 1);
        si = i + 1;
      }
    }
out();
    assert(ti + 3 <= si);
    // bring empty
    for (int i = 1; i < si; ++i) {
      for (int k = 0; k < K; ++k) {
        oper(i, i - 1);
        if (i >= 2) {
          oper(i - 1, i - 2);
        }
      }
    }
out();
    // swap rows
    for (int i = si; i > ti + 3; --i) {
      assert(L[i - 3] == K);
      assert(L[i - 2] == 0);
      assert(L[i - 1] == 0);
      assert(L[i] == K);
      for (int k = 0; k < K; ++k) {
        oper(i - 3, i - 2);
      }
      oper(i - 2, i - 1);
      for (int k = 0; k < K; ++k) {
        oper(i, i - 1);
        oper(i - 1, i - 2);
        oper(i - 2, i - 3);
      }
      for (int k = 0; k < K - 1; ++k) {
        oper(i - 2, i - 1);
        oper(i - 1, i);
      }
      oper(i - 1, i);
      for (int k = 0; k < K; ++k) oper(i - 3, i - 2);
      for (int k = 0; k < K; ++k) oper(i - 2, i - 1);
    }
out();
    // move to top
    si = ti + 3;
    int sk = -1;
    for (int k = 0; k < L[si]; ++k) {
      if (B[si][k] == val) {
        sk = k;
        break;
      }
    }
    assert(~sk);
    for (; L[si] > sk; ) oper(si, si - 1);
    oper(si - 1, si - 2);
    for (int k = 0; k < K; ++k) oper(si - 1, si);
    oper(si - 2, si - 1);
    oper(si - 1, si);
    // go to target
    for (; L[ti] > tk; ) oper(ti, ti + 1);
    if (L[ti + 1] == K) oper(ti + 1, ti + 2);
    oper(si, si - 1);
    oper(si - 1, si - 2);
    oper(si - 2, si - 3);
    // ue tsumeru
    for (int i = ti + 1; i <= ti + 3; ++i) {
      for (int j = i; j > ti; --j) {
        for (int k = 0; k < K; ++k) oper(j, j - 1);
      }
    }
  }
out();
#ifdef LOCAL
cerr<<"move done"<<endl;
#endif
}
void solve() {
  ans.clear();
out();
  // flatten
  for (int i = N; i >= 0; --i) {
    for (int k = 0; k < K; ++k) {
      for (int j = i; j <= N; ++j) {
        oper(j, j + 1);
      }
    }
  }
out();
  for (int i = 0; i < N; ++i) {
    // ?
    for (int k = 0; k < K; ++k) oper(i + 2, i + 1);
    for (int k = 0; k < K; ++k) oper(i + 1, i);
    
    for (int k = 0; k < K; ++k) {
      // shita tsumeru
      for (int j = N + 1; j > i; --j) {
        for (int jj = j; jj <= N && jj <= j + 2; ++jj) {
          for (int l = 0; l < K; ++l) oper(jj, jj + 1);
        }
      }
      
      const int val = A[i + 1][K - 1 - k];
      for (int j = 0; j <= N + 1; ++j) {
        for (int l = 0; l < L[j]; ++l) {
          if (make_pair(i, k) <= make_pair(j, l) && val == B[j][l]) {
            move(i, k, j, val);
            goto found;
          }
        }
      }
      assert(false);
     found:{}
    }
  }
  // [0, N) -> [1, N]
  for (int i = N; --i >= 0; ) {
    for (int k = 0; k < K; ++k) {
      oper(i, i + 1);
    }
  }
out();
  for (int i = 1; i <= N; ++i) {
    assert(L[i] == K);
    for (int k = 0; k < K; ++k) {
      assert(A[i][k] == B[i][k]);
    }
  }
  
  assert((int)ans.size() <= 1'000'000);
  
  reverse(ans.begin(), ans.end());
  puts("TAK");
  printf("%d\n", (int)ans.size());
  for (const auto &op : ans) {
    printf("%d %d\n", op.second, op.first);
  }
  
#ifdef LOCAL
judge();
#endif
}

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d", &N, &K);
    for (int i = 1; i <= N; ++i) {
      for (int k = 0; k < K; ++k) {
        scanf("%d", &A[i][k]);
      }
    }
    
    if (K == 1) {
      puts("TAK");
      puts("0");
    } else {
      map<int, vector<pair<int, int>>> ikss;
      for (int i = 1; i <= N; ++i) {
        for (int k = 0; k < K; ++k) {
          ikss[A[i][k]].emplace_back(i, k);
        }
      }
      // (freq, key)
      vector<pair<int, int>> target;
      for (const auto &kv : ikss) {
        const int len = kv.second.size();
        const int num = (len + K - 1) / K;
        for (int p = 0; p < num; ++p) {
          target.emplace_back(min(K * (p + 1), len) - K * p, kv.first);
        }
      }
// cerr<<"target = "<<target<<endl;
      if ((int)target.size() <= N + 2) {
        fill(L, L + (N + 2), 0);
        for (int i = 0; i < (int)target.size(); ++i) {
          L[i] = target[i].first;
          fill(B[i], B[i] + L[i], target[i].second);
        }
        solve();
      } else {
        puts("NIE");
      }
    }
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}