#include <bits/stdc++.h>
using namespace std;
int t,n,k,a[55][15],cnt[55],mv[1000011][2],nmv;map<int,int> mp;
bool nd[55][15],mk[55][15];
void move(int x,int y)
{
	a[y][++cnt[y]]=a[x][cnt[x]--];
	mk[y][cnt[y]]=mk[x][cnt[x]+1];mk[x][cnt[x]+1]=0;
	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)
{
	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(mk[i][_]&&cur<k-1)++cur,nd[i][_]=1;else nd[i][_]=0;
		for(int _=1;_<=cnt[i];++_)if(mk[i][_])++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(mk[i][_]&&!flg)nd[i][_]=flg=1;else nd[i][_]=0;
		}
		SingleCleanse(x-1);
		if(mk[x-1][cnt[x-1]])move(x-1,x);
		else
		{
			while(cnt[x-2]==k)MoveL(x-2);
			move(x-1,x-2);move(x-1,x);
		}
	}
	while(cnt[0])MoveR(0);
	while(cnt[1])MoveR(1);
	memset(mk,0,sizeof(mk));
}
void Sort(int x)
{
	if(!cnt[x])return;
	int mx=0;
	for(int i=1;i<=cnt[x];++i)mx=max(mx,a[x][i]);
	while(cnt[x])
	{
		if(a[x][cnt[x]]==mx)move(x,x-1),move(x-1,x-2);
		else move(x,x-1);
	}
	while(cnt[x-1])move(x-1,x);
	Sort(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+2){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;++_)
			{
				int cur=0;
				for(int i=0;i<=ed;++i)
				{
					for(int j=1;j<=cnt[i];++j)
					{
						if(cur<n&&a[i][j]==x.first)mk[i][j]=1;else mk[i][j]=0;
					}
				}
				FullCleanse(ed--);
			}
		}
		int ted=ed,cur=0;
		for(auto x:mp)
		{
			bool flg=1;
			while(flg)
			{
				flg=0;
				for(int i=0;i<=ed;++i)
				{
					for(int j=1;j<=cnt[i];++j)
					{
						if(a[i][j]==x.first)
						{
							++cur;mk[i][j]=1;
							if(cur==k){flg=1;cur=0;FullCleanse(ed--);break;}
						}
					}
					if(flg)break;
				}
			}
		}
		if(cur)FullCleanse(ed--);
		++ed;
		for(int i=2;i<=ted;++i)Sort(i);
		int lst=-1,lstp=ted+1;
		for(int i=ted-2;~i;--i)
		{
			while(cnt[i]&&lstp!=i)
			{
				while(a[i][cnt[i]]==lst)for(int _=i;_<lstp;++_)move(_,_+1);
				if(cnt[i])lst=a[i][cnt[i]],--lstp;
			}
		}
		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;
}