#include<bits/stdc++.h>
#define W while
#define RI int
#define Cn const
#define CI Cn int& 
#define I inline
using namespace std;
Cn int N=2e6+10,M=610;
int Tt,n,m,k,a[N],bl[M],hd[N];
vector<int> stk[M],ed[N];
struct node{int o,x,y;};
vector<node> A;
#define pb push_back
I void POPF(CI x){
	if(stk[x].size()==1) stk[x].clear();
	else{RI t=stk[x][1];stk[x].clear(),stk[x].pb(t);}
}
I void Sol1(){
	RI i;for(i=1;i<=k;i++) bl[i]=(i+1)/2;
	for(i=1;i<=m;i++) if(stk[bl[a[i]]].size()&&stk[bl[a[i]]].back()==a[i]) A.pb((node){1,bl[a[i]],0}),stk[bl[a[i]]].pop_back();
	else if(stk[bl[a[i]]].size()&&stk[bl[a[i]]][0]==a[i]) A.pb((node){1,n,0}),A.pb((node){2,bl[a[i]],n}),POPF(bl[a[i]]);
	else A.pb((node){1,bl[a[i]],0}),stk[bl[a[i]]].pb(a[i]);
}
int cnt[M],rk[N];
deque<int> sk[M];
I void CK(RI x);
I void UPD(RI x){
//	cerr<<"UPD "<<x<<"\n";
	if(sk[x].empty()) return ;
	RI t=sk[x].back();hd[t]=x;
	t=sk[x].front();
	for(auto i:ed[t]) if(i==x) return ;
	ed[t].pb(x);
	if(ed[t].size()>=2){
//		cerr<<ed[t][0]<<" "<<ed[t][1]<<"\n";
//		cerr<<"PREPAR "<<t<<"\n";
		CK(t);
	}
//	CK(t);
//	sort(ed[t].begin(),ed[t].end());
//	ed[t].erase(unique(ed[t].begin(),ed[t].end()),ed[t].end());
//	if(ed[t].size()>=2) CK(t);
}
I void Prt(){
	cerr<<"RT";
	RI i;for(i=1;i<=n;i++){
		putchar('[');
		W(!sk[i].empty()) printf("%d, ",sk[i].back()),sk[i].pop_back();
		printf("]\n");
	}
	cerr<<"GD";
	puts("ED:");
//	cerr<<hd[5]<<"\n";
	for(i=1;i<=k;i++){
		putchar('[');
		for(auto j:ed[i]) printf("%d, ",j);
		printf("]\n");
	}
}
I void DELF(RI x){
	if(sk[x].empty()) return ;
	RI t=sk[x].front();
	vector<int> tv;
	for(auto i:ed[t]) if(i^x) tv.pb(i);
	ed[t]=tv;
	cnt[t]--;
	sk[x].pop_front();
	if(sk[x].empty()) hd[t]=0;
	else{
		t=sk[x].front();
		for(auto i:ed[t]) if(i==x) return ;
		ed[t].pb(x);
	}
}
I void CK(RI x){
//	cerr<<"CK "<<x<<"\n";
	if(ed[x].size()<2) return ;
	RI a=ed[x][0],b=ed[x][1];
//	if(a==b) cerr<<x<<"\n";
//	cerr<<x<<" "<<a<<" "<<b<<"\n";
//	cerr<<sk[a].front()<<" "<<sk[b].front()<<"\n";
//	if(sk[a].front()^sk[b].front()) return ;
	assert(sk[a].front()==sk[b].front());
	A.pb((node){2,a,b});
//	cerr<<"CKD "<<x<<"\n";
	DELF(a),DELF(b);
//	cerr<<"CKU "<<x<<"\n";
	UPD(a),UPD(b);
//	cerr<<"CKE "<<x<<"\n";
	if(!sk[a].empty()) CK(sk[a].front());
	if(!sk[b].empty()) CK(sk[b].front());
//	cerr<<"CKKK "<<x<<"\n";
//	Prt();exit(0);
}
I void CLH(RI x){
	if(sk[x].empty()) return ;
	hd[sk[x].back()]=0;
}
I void DEL(CI x,CI y){
	vector<int> tv;
	for(auto i:ed[x]) if(i^y) tv.pb(i);
	ed[x]=tv;
}
I void Sol2(){
	RI i;for(i=1;i<=k;i++) cnt[i]=0,hd[i]=0,ed[i].clear(),sk[i].clear();
	for(i=1;i<=m;i++) if(hd[a[i]]) A.pb((node){1,hd[a[i]],0}),DEL(sk[hd[a[i]]].back(),hd[a[i]]),sk[hd[a[i]]].pop_back(),cnt[a[i]]--,UPD(hd[a[i]]),hd[a[i]]=0;
	else if(!cnt[a[i]]) A.pb((node){1,1,0}),CLH(1),rk[a[i]]=++rk[0],sk[1].pb(a[i]),hd[a[i]]=1,cnt[a[i]]++,UPD(1);else{
		RI X=-1,j;
		CK(15);
		for(j=2;j<=n;j++) if(!sk[j].empty()&&rk[sk[j].back()]<=rk[a[i]]){
			if(!~X) X=j;else rk[sk[j].back()]>rk[sk[X].back()]&&(X=j);
		}
		if(!~X){
			for(j=2;j<=n;j++) if(sk[j].empty()){X=j;break ;}
		}
//		RI l=2,r=n,mid,X=-1;W(l<=r) mid=l+r>>1,(sk[mid].empty()||rk[sk[mid].back()]<=rk[a[i]])?X=mid,r=mid-1:l=mid+1;
//		cerr<<"?? "<<X<<" "<<ed[1]<<"\n";
		!~X&&(Prt(),0);
		assert(~X);
		++cnt[a[i]];CLH(X),sk[X].pb(a[i]),A.pb((node){1,X,0}),UPD(X),!sk[X].empty()&&(CK(sk[X].front()),0);
	}//Prt();
}
I void Sol(){
	RI i;scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++) scanf("%d",&a[i]);
	if(k==2*n-2) Sol1();else Sol2();
	printf("%d\n",A.size());for(auto i:A) i.o&1?printf("%d %d\n",i.o,i.x):printf("%d %d %d\n",i.o,i.x,i.y);
//	exit(0);
}
int main(){
	freopen("meow.in","r",stdin);freopen("meow.out","w",stdout);
	scanf("%d",&Tt);W(Tt--) Sol();
}