#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
int read(){
	char c=getchar();int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return f==1?x:~x+1;
}
int T;
int n,m,k;
int a[2000010];
int pp[2000010];
int lst[2000010];
PII stk[300010][3];
PII pos[100010];
//int idx[310];
struct ope{
	int op,s1,s2;
};
int main(){
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	T=read();
	while(T--){
		n=read(),m=read(),k=read();
		for(int i=1;i<=n;++i) stk[i][0]=stk[i][1]=stk[i][2]=mp(0,0);
		for(int i=1;i<=k;++i) lst[i]=0,pos[i]=mp(0,0);
		for(int i=1;i<=m;++i){
			pp[i]=0;
			a[i]=read();
			if(lst[a[i]]){
				pp[lst[a[i]]]=i;pp[i]=lst[a[i]];
				lst[a[i]]=0;
			}
			else lst[a[i]]=i;
		}
		if(n==1){
			vector<ope>ans;
			for(int i=1;i<=m;++i) ans.pb(ope{1,1});
			printf("%d\n",ans.size());
			for(ope i:ans){
				if(i.op==1) printf("%d %d\n",i.op,i.s1);
				else printf("%d %d %d\n",i.op,i.s1,i.s2);
			}
			continue ;
		}
		vector<ope>ans;
		set<PII>st;set<int>ca;
		int emp=1;
		for(int i=2;i<=n;++i) st.insert(mp(i,0)),st.insert(mp(i,1));
		int cnt=0,po=-1;
		for(int i=1;i<=m;++i){
//			printf("i:%d,%d\n",i,pp[i]);
			if(pp[i]>i){
				if(!st.empty()){
					PII it=(*st.begin());
					ans.pb(ope{1,it.fi});
					pos[a[i]]=it;stk[it.fi][it.se]=mp(a[i],i);
					st.erase(it);
				}
				else{
					vector<ope>tmp;
					int j=i;
					while(j!=n){
						++j;
						if(pp[j]==i) break ;
						if(pp[j]<j&&pos[a[j]].se==0){
							break ;
						}
					}
					int x=pos[a[j]].fi;
					if(pp[j]==i){
//						cerr<<"case1\n";
						ans.pb(ope{1,emp});
						for(int l=i+1;l<j;++l){
							if(pp[l]>l){
								if(!st.empty()){
									PII it=(*st.begin());
									ans.pb(ope{1,it.fi});
									pos[a[l]]=it;stk[it.fi][it.se]=mp(a[l],l);
									if(it.se==1){
										cnt+=(pp[l]<pp[stk[it.fi][0].se]);
									}
									st.erase(it);
								}
							}
							else{
								if(pos[a[l]].se==1){
									ans.pb(ope{1,pos[a[l]].fi});
									st.insert(pos[a[l]]);
									stk[pos[a[l]].fi][pos[a[l]].se]=mp(0,0);--cnt;
									pos[a[l]]=mp(0,0);
								}
							}
						}
						ans.pb(ope{1,emp});
					}
					else if(pp[stk[x][1].se]>j){//down first.
//						cerr<<"case2\n";
						ans.pb(ope{1,x});
						for(int l=i+1;l<j;++l){
							if(pp[l]>l){
								if(!st.empty()){
									PII it=(*st.begin());
									ans.pb(ope{1,it.fi});
									pos[a[l]]=it;stk[it.fi][it.se]=mp(a[l],l);
									if(it.se==1){
										cnt+=(pp[l]<pp[stk[it.fi][0].se]);
									}
									st.erase(it);
								}
							}
							else{
								if(pos[a[l]].se==1){
									ans.pb(ope{1,pos[a[l]].fi});
									st.insert(pos[a[l]]);
									stk[pos[a[l]].fi][pos[a[l]].se]=mp(0,0);--cnt;
									pos[a[l]]=mp(0,0);
								}
							}
						}
						ans.pb(ope{1,emp});
						ans.pb(ope{2,x,emp});
						pos[stk[x][0].fi]=mp(0,0);
						stk[x][0]=stk[x][1];stk[x][1]=mp(a[i],i);
						pos[stk[x][0].fi]=mp(x,0);
						pos[a[i]]=mp(x,1);
					}
					else{
//						cerr<<"case3\n";
						int p=pp[stk[x][1].se];
						ans.pb(ope{1,emp});stk[emp][0]=mp(a[i],i);pos[a[i]]=mp(emp,0);
						for(int l=i+1;l<p;++l){
							if(pp[l]>l){
								if(!st.empty()){
									PII it=(*st.begin());
									ans.pb(ope{1,it.fi});
									pos[a[l]]=it;stk[it.fi][it.se]=mp(a[l],l);
									if(it.se==1){
										cnt+=(pp[l]<pp[stk[it.fi][0].se]);
									}
									st.erase(it);
								}
							}
							else{
								if(pos[a[l]].se==1){
									ans.pb(ope{1,pos[a[l]].fi});
									st.insert(pos[a[l]]);
									stk[pos[a[l]].fi][pos[a[l]].se]=mp(0,0);
									pos[a[l]]=mp(0,0);
								}
							}
						}
						ans.pb(ope{1,x});
						pos[stk[x][1].fi]=mp(0,0);stk[x][1]=mp(0,0);
						st.insert(mp(emp,1));emp=x;
						for(int l=p+1;l<j;++l){
							if(pp[l]>l){
								if(!st.empty()){
									PII it=(*st.begin());
									ans.pb(ope{1,it.fi});
									pos[a[l]]=it;stk[it.fi][it.se]=mp(a[l],l);
									if(it.se==1){
										cnt+=(pp[l]<pp[stk[it.fi][0].se]);
									}
									st.erase(it);
								}
							}
							else{
								if(pos[a[l]].se==1){
									ans.pb(ope{1,pos[a[l]].fi});
									st.insert(pos[a[l]]);
									stk[pos[a[l]].fi][pos[a[l]].se]=mp(0,0);
									pos[a[l]]=mp(0,0);
								}
							}
						}
						ans.pb(ope{1,x});
						pos[stk[x][0].fi]=mp(0,0);stk[x][0]=mp(0,0);
					}
					i=j;
				}
			}
			else{
				if(pos[a[i]].se==1){
					ans.pb(ope{1,pos[a[i]].fi});
					st.insert(pos[a[i]]);
					stk[pos[a[i]].fi][pos[a[i]].se]=mp(0,0);
					pos[a[i]]=mp(0,0);
				}
				else if(emp){
					ans.pb(ope{1,emp});
					ans.pb(ope{2,emp,pos[a[i]].fi});
					stk[pos[a[i]].fi][0]=stk[pos[a[i]].fi][1];
					if(stk[pos[a[i]].fi][1].fi){
						pos[stk[pos[a[i]].fi][1].fi]=pos[a[i]];
						stk[pos[a[i]].fi][1]=mp(0,0);
						st.insert(mp(pos[a[i]].fi,1));
					}
					else st.insert(pos[a[i]]);
					pos[a[i]]=mp(0,0);
				}
			}
		}
		printf("%d\n",ans.size());
		for(ope i:ans){
			if(i.op==1) printf("%d %d\n",i.op,i.s1);
			else printf("%d %d %d\n",i.op,i.s1,i.s2);
		}
	}
}