#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 50 + 5;
const int MAXD = 10 + 5;
const int MAXP = MAXN * MAXD;

using Data = array<int,2>;

int n,d,pcnt;
vector<int> a[MAXN];
int c[MAXP];
Data pos[MAXP], need[MAXP];

vector<pii> ans, finans;

bool solve_finans(void)
{
	static vector<int> b[MAXN];
	for(int i=0; i<=n+1; ++i)
		b[i].clear();
	
	static int id[MAXP];
	iota(id+1, id+pcnt+1, 1);
	sort(id+1, id+pcnt+1, [&] (int x,int y){
		return c[x] < c[y];
	});
	
	int cur = 0;
	for(int i=1; i<=pcnt && cur<=n+1; ++i)
	{
		int u = id[i], v = id[i-1];
		if((i > 1 && c[u] != c[v]) || (int)b[cur].size() == d) ++cur;
		if(cur > n+1) break;
		b[cur].emplace_back(u);
	}
	if(cur > n+1)
		return 0;
	
	while(1)
	{
		int i = 1;
		while(i<=n+1 && ((int)b[i].size() == 0 || (int)b[i-1].size() == d)) ++i;
		if(i > n+1) break;
		finans.emplace_back(i, i-1);
		b[i-1].emplace_back(b[i].back());
		b[i].pop_back();
	}
	
	for(int i=n; i>=1; --i)
	{
		for(int j=1; j<=d; ++j)
		{
			finans.emplace_back(i-1, i);
			b[i].emplace_back(b[i-1].back());
			b[i-1].pop_back();
		}
	}
	
	for(int i=1; i<=n; ++i)
	{
		assert((int)b[i].size() == d);
		for(int j=0; j<d; ++j)
			need[b[i][j]] = {i,j};
	}
	
	return 1;
}

void OP(int i,int j)
{
	assert((int)a[i].size() && (int)a[j].size() < d);
	ans.emplace_back(i, j);
	int u = a[i].back(); a[i].pop_back();
	a[j].emplace_back(u);
	pos[u] = {j, (int)a[j].size() - 1};
}
void OP(int i,int j,int k)
{
	while(k--) OP(i, j);
}

void move_empty(int i,int j)
{
	if(i <= j)
	{
		for(int k=i; k<j; ++k)
			OP(k+1, k, d);
	}
	else
	{
		for(int k=i; k>j; --k)
			OP(k-1, k, d);
	}
}

void move_single(int x, int beg, int enn)// beg <= enn
{
	if(beg == enn) return;
	
	int t1 = d-1 - enn;
	int t2 = enn - beg;
	
	OP(x, x+1, t1);
	OP(x, x-1, t2);
	
	OP(x, x+1);
	
	OP(x-1, x, t2);
	OP(x+1, x, t1+1);
}

void move_special(int x)// d, 1, 0, d-1
{
	for(int i=1; i<=d; ++i)
		OP(x-2, x-1), OP(x-1, x);
	OP(x, x+1);
	OP(x-1, x-2);
}

void solve(void)
{
	scanf("%d%d",&n,&d);
	pcnt = n * d;
	for(int i=1; i<=n; ++i)
	{
		a[i].resize(d);
		for(int j=0; j<d; ++j)
		{
			int u = (i-1) * d + j + 1;
			scanf("%d",&c[u]);
			a[i][j] = u;
			pos[u] = {i, j};
		}
	}
	a[0].clear();
	a[n+1].clear();
	
	if(d == 1)
	{
		printf("TAK\n");
		printf("0\n");
		return;
	}
	
	ans.clear(); finans.clear();
	
	if(solve_finans() == 0)
	{
		printf("NIE\n");
		return;
	}
	
	for(int needx=1; needx<=n; ++needx)
		for(int needy=d-1; needy>=0; --needy)
		{
			int u = 1;
			while(u<=pcnt && need[u] != Data{needx, needy}) ++u;
			
			assert(u <= pcnt);
			
			int curx = pos[u][0], cury = pos[u][1];
			if(curx == needx && cury == needy) continue;
			
			move_empty(0, curx-1);
			move_empty(n+1, curx+1);
			
//			printf("ok1\n");
			
			if(curx == needx)
			{
				move_single(curx, cury, needy);
				move_empty(curx-1, 0);
				move_empty(curx+1, n+1);
//				printf("fin\n");
				continue;
			}
			
//			printf("ok2\n");
			
			for(int i=d-1; i>=0; --i)
				OP(curx, i == cury? curx-1: curx+1);
			
//			printf("ok3\n");
//			
//			printf("curx = %d, needx = %d\n",curx,needx);
			
			for(int i=curx; i>needx+1; --i)
				move_special(i);
			
//			printf("ok4\n");
			
//			for(int i=-1; i<=2; ++i)
//				printf("siz[%d] = %d\n",needx+i,(int)a[needx+i].size());
			
			OP(needx-1, needx);
			OP(needx, needx+1);
			OP(needx+1, needx+2);
			
			OP(needx, needx-1);
			move_empty(needx, needx-1);
			
//			printf("ok5\n");
			
			move_single(needx, 0, needy);
			
			move_empty(needx-1, 0);
			move_empty(needx+1, n+1);
		}
	
	reverse(finans.begin(), finans.end());
	for(auto t: finans)
		ans.emplace_back(t.second, t.first);
	
	printf("TAK\n");
	printf("%d\n",(int)ans.size());
	for(auto t: ans)
		printf("%d %d\n",t.first,t.second);
}

int main(void)
{
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}