#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=2e6+10;
int n,m,k,cnt,a[N],ins[N],op[N<<1];
int vis[N],t[N],s[N],loc[N<<1],anl[N<<1];
deque<int>dq[5];
queue<int>q[2];
int read(){
	char ch=getchar();
	int x=0;
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
bool check(){
	while(!dq[1].empty())dq[1].pop_front();
	while(!dq[2].empty())dq[2].pop_front();
	while(!dq[3].empty())dq[3].pop_front();
	cnt=0;
	for(int i=1;i<=m;i++){
		op[++cnt]=1,loc[cnt]=ins[i];
		if(!dq[ins[i]].empty()&&dq[ins[i]].back()==a[i]){
			dq[ins[i]].pop_back();
			continue;
		}
		dq[ins[i]].push_back(a[i]);
		for(int j=1;j<=3;j++){
			if(ins[i]!=j&&!dq[j].empty()&&dq[j].front()==dq[ins[i]].front()){
				dq[j].pop_front(),dq[ins[i]].pop_front();
				op[++cnt]=2,loc[cnt]=j,anl[cnt]=ins[i];
				break;
			}
		}
	}
	if(!dq[1].empty()||!dq[2].empty()||!dq[3].empty())return false;
	return true;
}
bool dfs(int p){
	if(p==m+1)return check();
	ins[p]=1;
	if(dfs(p+1))return true;
	ins[p]=2;
	if(dfs(p+1))return true;
	ins[p]=3;
	if(dfs(p+1))return true;
	return false;
}
int main(){
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	int T=read();
	while(T--){
		n=read(),m=read(),k=read();
		for(int i=1;i<=m;i++)a[i]=read();
		if(n==2){
			cout<<m/2*3<<endl;
			while(!q[0].empty())q[0].pop();
			while(!q[1].empty())q[1].pop();
			for(int i=1;i<=m;i++){
				if(q[0].empty()||q[0].front()!=a[i]){
					cout<<"1 1\n";
					q[0].push(a[i]);
				}
				else{
					q[0].pop();
					cout<<"1 2\n2 1 2\n";
				}
			}
			continue;
		}
		else
		if(m<=14){
			dfs(1);
			for(int i=1;i<=cnt;i++){
				cout<<op[i]<<' ';
				if(op[i]==1)cout<<loc[i]<<'\n';
				else cout<<loc[i]<<' '<<anl[i]<<endl;
			}
			continue;
		}
		while(!q[0].empty())q[0].pop();
		while(!q[1].empty())q[1].pop();
		for(int i=1;i<=n;i++)q[0].push(i),q[1].push(i);
		for(int i=1;i<=2*n;i++)
			vis[i]=s[i]=loc[i]=t[i]=0;
		for(int i=m;i>=1;i--){
			if(s[a[i]]){
				if(!vis[s[a[i]]])q[0].push(s[a[i]]);
				else
				if(vis[s[a[i]]]==a[i])vis[s[a[i]]]=0,q[1].push(s[a[i]]);
				else{
					int k1=vis[s[a[i]]],k2=t[s[a[i]]];
					if(!q[0].empty()){
						vis[s[a[i]]]=0,t[s[a[i]]]=0;
						q[1].push(s[a[i]]);
						int nxt=q[0].front();q[0].pop();
						s[k1]=nxt,loc[k2]=nxt;
					}
					else{
						vis[s[a[i]]]=0,t[s[a[i]]]=0;
						q[1].push(s[k1]);
						int nxt=q[1].front();q[1].pop();
						s[k1]=nxt,loc[k2]=nxt;
						t[s[k1]]=k2,vis[s[k1]]=k1;
					}
				}
				loc[i]=s[a[i]],s[a[i]]=0;
			}
			else{
				if(!q[0].empty())s[a[i]]=loc[i]=q[0].front(),q[0].pop();
				else{
					int temp=q[1].front();
					loc[i]=s[a[i]]=temp;
					vis[temp]=a[i],t[temp]=i;
					q[1].pop();
				}
			}
		}
		cout<<m<<endl;
		for(int i=1;i<=m;i++)
			cout<<1<<' '<<loc[i]<<endl;
	}
	return 0;
}