#include<bits/stdc++.h>
using namespace std;
inline long long read(){
	long long x=0,f=1;char ch=getchar();
	while ((!isdigit(ch))&&(ch!='-')) ch=getchar();
	if (ch=='-') f=-1,ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}
struct node {
	long long x,y,z;
};
node Z;
vector<node> Q;
bool vis[1001010];
long long height[1001010];
long long fre[1001001],bel[1001010][2],a[1001010];
long long nnn,siz,nowtop,n,m,K,i,num;
void Subtask1(){
	for (i=1;i<=K;i++) vis[i]=false,fre[i]=0;
	for (i=1;i<=K;i++) bel[i][0]=bel[i][1]=0;
	for (i=1;i<=m;i++) a[i]=read();
	for (i=1;i<n;i++) height[i]=0;
	Q.clear();
	num=0;
	for (i=1;i<=m;i++){
		fre[a[i]]++;
		
		if (fre[a[i]]&1){
			if (vis[a[i]]==false)
			    {
		        num++;
			    bel[a[i]][0]=(num-1)/2+1;
			    bel[a[i]][1]=(num-1) % 2+1;  
			    vis[a[i]]=true;
		        }
		    else {
		    	nowtop=height[bel[a[i]][0]];
		    	if (nowtop==0) bel[a[i]][1]=1;
		    	else bel[a[i]][1]=2;
		    	height[bel[a[i]][0]]++;
			}
			Z.x=1;Z.y=bel[a[i]][0];Z.z=0;
			Q.push_back(Z);
		}
		else {
			if (bel[a[i]][1]==1) {
				Z.x=1;Z.y=n;Z.z=0;
				Q.push_back(Z);
				Z.x=2;Z.y=bel[a[i]][0];Z.z=n;
				Q.push_back(Z);
			}
			else 
			    {
			    Z.x=1;Z.y=bel[a[i]][0];Z.z=0;
				Q.push_back(Z);
			    
				}
			height[bel[a[i]][0]]--;
		}
	}
	nowtop=Q.size();
	printf("%lld\n",nowtop);
	for (i=0;i<Q.size();i++)
	     if (Q[i].x==1) printf("%lld %lld\n",Q[i].x,Q[i].y);
	     else printf("%lld %lld %lld\n",Q[i].x,Q[i].y,Q[i].z);
	return ;
}
/*
void Subtask3(){
	for (i=1;i<=3;i++) vis[i]=false;
	for (i=1;i<=m;i++) a[i]=read();
	m=read();
	for (i=1;i<=m;i++) a[i]=read();
		for (i=1;i<=K;i++) vis[i]=false,fre[i]=0;
	for (i=1;i<=K;i++) bel[i][0]=bel[i][1]=0;
	for (i=1;i<=m;i++) a[i]=read();
	for (i=1;i<n;i++) height[i]=0;
	Q.clear();
	num=0;siz=0;
	for (i=1;i<=m;i++){
		fre[a[i]]++;
		
		if (fre[a[i]]&1){
			siz++;
			if (siz==2*n-1){
				if ((bel[a[i+1]][1]==1)){
					Z.x=1;Z.y=bel[a[i+1]][0];
					Q.push_back(Z);
				}
				else {
					flag=false;nnn=0;
					for (j=i+1;j<=m;j++)
					     if (bel[a[j]][1]==1) {
					     	nnn=bel[a[j]][0];break;
						 }
					Z.x=1;Z.y=nnn;
					Q.push_back(Z);
				}
				continue;
			}
			if (vis[a[i]]==false)
			    {
		        num++;
			    bel[a[i]][0]=(num-1)/2+1;
			    bel[a[i]][1]=(num-1) % 2+1;  
			    vis[a[i]]=true;
		        }
		    else {
		    	nowtop=height[bel[a[i]][0]];
		    	if (nowtop==0) bel[a[i]][1]=1;
		    	else bel[a[i]][1]=2;
		    	height[bel[a[i]][0]]++;
			}
			Z.x=1;Z.y=bel[a[i]][0];Z.z=0;
			Q.push_back(Z);
		}
		else {
			siz--;
			if (bel[a[i]][1]==1) {
				Z.x=1;Z.y=n;Z.z=0;
				Q.push_back(Z);
				Z.x=2;Z.y=bel[a[i]][0];Z.z=n;
				Q.push_back(Z);
			}
			else 
			    {
			    Z.x=1;Z.y=bel[a[i]][0];Z.z=0;
				Q.push_back(Z);
			    
				}
			height[bel[a[i]][0]]--;
		}
	}
	nowtop=Q.size();
	printf("%lld\n",nowtop);
	for (i=0;i<Q.size();i++)
	     if (Q[i].x==1) printf("%lld %lld\n",Q[i].x,Q[i].y);
	     else printf("%lld %lld %lld\n",Q[i].x,Q[i].y,Q[i].z);
	return ;
}*/
void Subtask2(){
	if (n==2){
		//Subtask3();
		return ;
	}
	for (i=1;i<=m;i++) a[i]=read();
		for (i=1;i<=K;i++) vis[i]=false,fre[i]=0;
	for (i=1;i<=K;i++) bel[i][0]=bel[i][1]=0;
	for (i=1;i<=m;i++) a[i]=read();
	for (i=1;i<n;i++) height[i]=0;
	Q.clear();
	num=0;siz=0;
	for (i=1;i<=m;i++){
		fre[a[i]]++;
		
		if (fre[a[i]]&1){
			siz++;
			if (siz==2*n-1){
				if ((bel[a[i+1]][1]==1)){
					Z.x=1;Z.y=bel[a[i+1]][0];
					bel[a[i]][0]=bel[a[i+1]][0];
					Q.push_back(Z);
				}
				else {
				}
				continue;
			}
			if (vis[a[i]]==false)
			    {
		        num++;
			    bel[a[i]][0]=(num-1)/2+1;
			    bel[a[i]][1]=(num-1) % 2+1;  
			    vis[a[i]]=true;
		        }
		    else {
		    	nowtop=height[bel[a[i]][0]];
		    	if (nowtop==0) bel[a[i]][1]=1;
		    	else bel[a[i]][1]=2;
		    	height[bel[a[i]][0]]++;
			}
			Z.x=1;Z.y=bel[a[i]][0];Z.z=0;
			Q.push_back(Z);
		}
		else {
			siz--;
			if (bel[a[i]][1]==1) {
				Z.x=1;Z.y=n;Z.z=0;
				Q.push_back(Z);
				Z.x=2;Z.y=bel[a[i]][0];Z.z=n;
				Q.push_back(Z);
			}
			else 
			    {
			    Z.x=1;Z.y=bel[a[i]][0];Z.z=0;
				Q.push_back(Z);
			    
				}
			height[bel[a[i]][0]]--;
		}
	}
	nowtop=Q.size();
	printf("%lld\n",nowtop);
	for (i=0;i<Q.size();i++)
	     if (Q[i].x==1) printf("%lld %lld\n",Q[i].x,Q[i].y);
	     else printf("%lld %lld %lld\n",Q[i].x,Q[i].y,Q[i].z);
	return ;
}
void Main(){
	n=read();m=read();K=read();
	if (K==2*n-2) Subtask1();
	else Subtask2();
	return ;
}
int main(){
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	int Testing=read();
	for (;Testing;Testing--) Main();
	return 0;
}
