#include <bits/stdc++.h>
using namespace std;
int t,n,k,a[111][111],cnt[111],mv[1000011][2],nmv;map<int,int> mp;
bool nd[111][111];
void move(int x,int y)
{
	a[y][++cnt[y]]=a[x][cnt[x]--];
	a[x][cnt[x]+1]=0;
	++nmv;mv[nmv][0]=x;mv[nmv][1]=y;
}
void MoveL(int x)
{
	if(cnt[x-1]==k)MoveL(x-1);
	move(x,x-1);
}
void MoveR(int x)
{
	if(cnt[x+1]==k)MoveR(x+1);
	move(x,x+1);
}
void SingleCleanse(int x)
{
	for(int i=2;i<=x;++i)
	{
		while(cnt[i])
		{
			if(nd[i][cnt[i]])move(i,i-1);
			else move(i,i-1),move(i-1,i-2);
		}
		while(cnt[i-1])move(i-1,i);
	}
}
void FullCleanse(int x,int aim)
{
	while(cnt[0])MoveR(0);
	while(cnt[1])MoveR(1);
	int cur=0,all=0;
	for(int i=2;i<=x;++i)
	{
		for(int _=1;_<=cnt[i];++_)if(a[i][_]==aim&&cur<k-1)++cur,nd[i][_]=1;else nd[i][_]=0;
		for(int _=1;_<=cnt[i];++_)if(a[i][_]==aim)++all;
	}
	SingleCleanse(x);
	if(all>=k)
	{
		while(cnt[0])MoveR(0);
		while(cnt[1]>1)MoveR(1);
		bool flg=0;
		for(int i=2;i<x;++i)
		{
			for(int _=1;_<=cnt[i];++_)if(a[i][_]==aim&&!flg)nd[i][_]=flg=1;else nd[i][_]=0;
		}
		SingleCleanse(x-1);
		if(a[x-1][cnt[x-1]]==aim)move(x-1,x);
		else
		{
			while(cnt[x-2]==k)MoveL(x-2);
			move(x-1,x-2);move(x-1,x);
		}
	}
}
int main()
{
	scanf("%d",&t);while(t--)
	{
		scanf("%d%d",&n,&k);mp.clear();cnt[0]=cnt[n+1]=0;
		for(int i=1;i<=n;++i)for(int j=1;j<=k;++j)scanf("%d",a[i]+j),++mp[a[i][j]];
		if(k==1){printf("TAK\n0\n");continue;}
		int ned=0;
		for(auto x:mp)ned+=(x.second+k-1)/k;
		if(ned>n){printf("NIE\n");continue;}
		nmv=0;
		for(int i=1;i<=n;++i)cnt[i]=k;
		int ed=n+1;
		for(auto x:mp)
		{
			for(int _=1;_<=(x.second+k-1)/k;++_)FullCleanse(ed--,x.first);
		}
		if(cnt[n+1])
		{
			for(int i=1;i<=n+1;++i)while(cnt[i])MoveL(i);
		}
		printf("TAK\n%d\n",nmv);
		for(int i=1;i<=nmv;++i)printf("%d %d\n",mv[i][0],mv[i][1]);
	}return 0;
}