#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
int n,k;
int a[55][15],top[55];
int b[55][15];
void solve(){
	memset(a,0,sizeof(a));memset(top,0,sizeof(top));
	cin>>n>>k;
	map<int,int> mp; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			cin>>a[i][j];
			mp[a[i][j]]++;
		} 
		top[i]=k;
	}
	if(k==1){cout<<"TAK"<<endl<<"0"<<endl;return;} 
	int cnt=0;
	for(auto i:mp) cnt+=(i.second+k-1)/k;
	if(cnt>n+2){cout<<"NIE"<<endl;return;} 
	cout<<"TAK"<<endl;
	int x=0,y=1;
	for(auto i:mp){
		while(i.second--){
			b[x][y++]=i.first;
			if(y==k+1) x++,y=1;
		}
	}
	vector<pair<int,int> > ans;
	auto op=[&](int x,int y){
		ans.push_back(MP(x,y));
		a[y][++top[y]]=a[x][top[x]--];a[x][top[x]+1]=0;
	};
	for(int i=n;i>=1;i--){
		for(int j=1;j<=k;j++) op(i,i+1);
	}
	for(int gx=0;gx<n;gx++){
		while(top[gx+1]){
			for(int j=n;j>=gx+1;j--) while(top[j]&&top[j+1]+1<=k) op(j,j+1);
		}
		for(int gy=1;gy<=k;gy++){
			int x=0,y=0;
			for(int p=gx+2;p<=n+1;p++) for(int q=1;q<=k;q++)
				if(a[p][q]==b[gx][gy]){
					x=p,y=q;
					goto nxt;
				}
			nxt:; 
			for(int i=gx+1;i<x-1;i++){
				while(top[i+1]) op(i+1,i);
			}
			while(x!=gx+2){
				if(y!=1||top[x]!=k){
					while(top[x]+1!=y) op(x,x-1);
					y=top[--x];
					while(top[x-1]){
						op(x-1,x);
						if(top[x+1]!=k) op(x,x+1);
					}
				}else{
					int pre=x-2;
					while(top[pre]==k) pre--;
					for(int i=pre;i<x-2;i++) op(i+1,i);
					op(x,x-1);op(x-1,x-2);
					while(top[x]) op(x,x-1);
					y=top[--x];
					while(top[x-1]) op(x-1,x),op(x,x+1);
					for(int i=x-2;i>=pre;i--) op(i,i+1);
					while(top[x-1]) op(x-1,x);
				} 
			}
			while(top[x]>=y) op(x,x-1);
			op(x-1,x-2);
			while(top[x-1]) op(x-1,x);
		}
	} 
	int ept=n+1;
	for(int i=n-1;i>=0;i--){
		for(int j=k;j>=1;j--){
			if(top[ept]==0||a[i][j]==a[ept][1]&&top[ept]<k){
				for(int t=i;t<ept;t++) op(t,t+1); 
			}else{
				ept--;
				for(int t=i;t<ept;t++) op(t,t+1); 
			}
		}
	}
	cout<<ans.size()<<endl;
	for(auto i:ans) cout<<i.first<<' '<<i.second<<endl; 
}
int main(){
	ios::sync_with_stdio(false);
	int _;cin>>_;
	while(_--) solve(); 
}