#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#endif
#define NDEBUG
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define each(x,v) for(auto&x:v)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
using namespace std;
using LL=long long;
template<class T>void rd(T&x){
	int f=0,c;
	while(!isdigit(c=getchar()))f^=!(c^45);
	x=(c&15);
	while(isdigit(c=getchar()))x=x*10+(c&15);
	if(f)x=-x;
}
const int N=605,maxK=605,M=2000005;
int T,n,m,K,a[M];
vector<int>bin[N];
int p0[maxK],p1[maxK];
queue<int>q[2];
int sz[2];
int get_any(int x){
	while(!q[x].empty()&&SZ(bin[q[x].front()])!=x)q[x].pop();
	if(q[x].empty())return -1;
	return q[x].front();
}
int ans[M<<1][2],top;
void ps(int x,int y=-1){
	ans[++top][0]=x,ans[top][1]=y;
}
void pop0(int x){
	if(!SZ(bin[x])){
		D("!\n");
	}
	assert(SZ(bin[x]));
	if(SZ(bin[x])<2){
		--sz[SZ(bin[x])];
	}
	rep(i,0,SZ(bin[x])-1){
		p0[bin[x][i]]=p1[bin[x][i]]=0;
	}
	bin[x].erase(bin[x].begin());
	rep(i,0,SZ(bin[x])-1){
		p0[bin[x][i]]=x;
		p1[bin[x][i]]=i;
	}
	if(SZ(bin[x])<2){
		q[SZ(bin[x])].push(x);
		++sz[SZ(bin[x])];
	}
}
void pop1(int x){
	if(SZ(bin[x])<2){
		--sz[SZ(bin[x])];
	}
	rep(i,0,SZ(bin[x])-1){
		p0[bin[x][i]]=p1[bin[x][i]]=0;
	}
	bin[x].pop_back();
	rep(i,0,SZ(bin[x])-1){
		p0[bin[x][i]]=x;
		p1[bin[x][i]]=i;
	}
	if(SZ(bin[x])<2){
		q[SZ(bin[x])].push(x);
		++sz[SZ(bin[x])];
	}
}
void put(int x,int y){
	if(SZ(bin[x])<2){
		--sz[SZ(bin[x])];
	}
	rep(i,0,SZ(bin[x])-1){
		p0[bin[x][i]]=p1[bin[x][i]]=0;
	}
	bin[x].pb(y);
	rep(i,0,SZ(bin[x])-1){
		p0[bin[x][i]]=x;
		p1[bin[x][i]]=i;
	}
	if(SZ(bin[x])<2){
		q[SZ(bin[x])].push(x);
		++sz[SZ(bin[x])];
	}
}
int vis[maxK],tot[maxK];
int main(){
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	rd(T);
	while(T--){
		top=0;
		rd(n),rd(m),rd(K);
		rep(i,1,m){
			rd(a[i]);
		}
		while(!q[0].empty())q[0].pop();
		while(!q[1].empty())q[1].pop();
		rep(i,1,n)q[0].push(i);
		sz[0]=sz[1]=0;
		sz[0]=n;
		
		rep(i,1,K)vis[i]=0;
		rep(i,1,m){
			if(p0[a[i]]){
				if(p1[a[i]]==0){
					int x=get_any(0);
					assert(x!=-1);
					ps(x);
					ps(x,p0[a[i]]);
					pop0(p0[a[i]]);
				}else{
					ps(p0[a[i]]);
					pop1(p0[a[i]]);
				}
			}else{
				int x=get_any(1);
				if(x!=-1){
					ps(x);
					put(x,a[i]);
					continue;
				}
				x=get_any(0);
				if(sz[0]!=1){
					ps(x);
					put(x,a[i]);
					continue;
				}
				int j=i+1;
				while(j<=m&&p0[a[j]]&&p1[a[j]]==1){
					if(vis[a[j]]!=i){
						vis[a[j]]=i;
						tot[a[j]]=0;
					}
					tot[a[j]]^=1;
					++j;
				}
				assert(j<=m);
				if(a[j]==a[i]){
					ps(x);
					rep(k,i+1,j-1){
						if(p0[a[k]]){
							ps(p0[a[k]]);
							pop1(p0[a[k]]);
						}else{
							int tmp=get_any(1);
							assert(tmp!=-1);
							ps(tmp);
							put(tmp,a[k]);
						}
					}
					ps(x);
				}else{
					assert(p0[a[j]]);
					int v1=a[j];
					assert(SZ(bin[p0[v1]])==2);
					int v2=bin[p0[v1]][1];
					if(tot[v2]){
						ps(p0[v1]);
						rep(k,i+1,j-1){
							if(p0[a[k]]){
								ps(p0[a[k]]);
								pop1(p0[a[k]]);
							}else{
								int tmp=get_any(1);
								assert(tmp!=-1);
								ps(tmp);
								put(tmp,a[k]);
							}
						}
						ps(p0[v1]);
						put(x,a[i]);
						pop0(p0[v1]);
					}else{
						int cur=p0[v1];
						ps(cur);
						rep(k,i+1,j-1){
							if(a[k]==v1){
								ps(cur);
							}else if(p0[a[k]]){
								ps(p0[a[k]]);
								pop1(p0[a[k]]);
							}else{
								int tmp=get_any(1);
								assert(tmp!=-1);
								ps(tmp);
								put(tmp,a[k]);
							}
						}
						ps(x);
						ps(x,cur);
						pop0(cur);
						put(cur,a[i]);
					}
				}
				i=j;
			}
		}
		printf("%d\n",top);
		rep(i,1,top){
			if(ans[i][1]==-1)printf("1 %d\n",ans[i][0]);else printf("2 %d %d\n",ans[i][0],ans[i][1]);
		}
	}
	return 0;
}
