#include<iostream>
#include<cstdio>
using namespace std;
int T;
bool b[1000005]={false};
bool c[1000005]={false};
int d[1000005];
struct ev
{
	int n;
	bool b;
	bool c;
}e[100005];
inline int read()
{
	char ch;int x=0,b=1;
	ch=getchar();
	while(ch>'9'||ch<'0')
		if(ch=='-')
		{
			b=-1;
			ch=getchar();
		}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*b;
}
long long op=0;
struct opp
{
	int n;
	int m1,m2;
}opp[1000005];
void workout()
{
	int n,k,m;
	n=read();
	m=read();
	k=read();
	int i,j;
	if(T%10==1)
	{
		int a;
		for(i=1;i<=m;i++)
		{
			a=read();
			if(!b[a])
			{
				b[a]=true;
				c[(a/2)+(a%2)]=a%2;
				op+=1;
				opp[op].n=1;
				opp[op].m1=(a/2)+(a%2);
			}
			else
			{
				if(c[(a/2)+(a%2)]==a%2)
				{
					op+=1;
					opp[op].n=1;
					opp[op].m1=(a/2)+(a%2);
					c[(a/2)+(a%2)]=!c[(a/2)+(a%2)];
				}
				else
				{
					op+=1;
					opp[op].n=1;
					opp[op].m1=n;
					op+=1;
					opp[op].n=2;
					opp[op].m1=(a/2)+(a%2);
					opp[op].m2=n;
				}
				b[a]=false;
			}
		}
	}
	else
	{
		int a,x;
		int i,j;
		bool o=false;
		for(i=1;i<=m;i++)
		{
			if(!o)
				a=read();
			else
			{
				a=x;
				o=false;
			}
			if(e[a].b==false)
			{
				x=read();
				if(e[x].b==false)
				{
					o=true;
					for(j=1;j<=n;i++)
					{
						if(d[j]<=2)
						{
							if(d[j]==0)
							{
								d[j]++;
								e[a].b=true;
								e[a].n=j;
								e[a].c=false;
								op++;
								opp[op].n=1;
								opp[op].m1=j;
							}
							else if(d[j]==1)
							{
								d[j]++;
								e[a].b=true;
								e[a].n=j;
								e[a].c=true;
								op++;
								opp[op].n=1;
								opp[op].m1=j;
							}
							break;
						}
					}
				}
				else
				{
					if(e[x].c||d[e[x].n]==1)
					{
						for(j=1;j<=n;j++)
						{
							if(j==e[x].n)j++;
							if(d[j]<=2)
							{
								if(d[j]==0)
								{
									d[j]++;
									e[a].b=true;
									e[a].n=j;
									e[a].c=false;
									op++;
									opp[op].n=1;
									opp[op].m1=j;
								}
								else if(d[j]==1)
								{
									d[j]++;
									e[a].b=true;
									e[a].n=j;
									e[a].c=true;
									op++;
									opp[op].n=1;
									opp[op].m1=j;
								}
								break;
							}
						}
						e[x].b=false;
						e[x].c=false;
						d[e[x].n]--;
						op++;
						opp[op].n=1;
						opp[op].m1=e[x].n;e[x].n=0;
						i++;
					}
					else
					{
						e[a].b=true;
						e[a].c=true;
						e[a].n=e[x].n;
						op++;
						opp[op].n=1;
						opp[op].m1=e[x].n;
						for(j=1;j<=m;j++)
						{
							if(e[j].n==e[x].n&&e[j].b)
							{
								e[j].c=false;
								break;
							}
						}
						for(j=1;j<=n;j++)
						{
							if(d[j]==0)
							{
								op++;
								opp[op].n=1;
								opp[op].m1=j;
								op++;
								opp[op].n=2;
								opp[op].m1=e[x].n;
								opp[op].m2=j;
								break;
							}
						}
						e[x].b=false;
						e[x].c=false;
						d[e[x].n]--;
						e[x].n=0;
						i++;
					}
				}
			}
			else
			{
				if(e[a].c||d[e[a].n]==1)
				{
					e[x].b=false;
					e[x].c=false;
					d[e[x].n]--;e[x].n=0;
					op++;
					opp[op].n=1;
					opp[op].m1=j;
					i++;
				}
				else
				{
					for(j=1;j<=n;j++)
					{
						if(d[j]==0)
						{
							op++;
							opp[op].n=1;
							opp[op].m1=j;
							op++;
							opp[op].n=2;
							opp[op].m1=e[x].n;
							opp[op].m2=j;
							break;
						}
					}
					e[x].b=false;
					e[x].c=false;
					e[x].n=0;
				}
			}
		}
	}
	return;
}
int main()
{
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	T=read();
	int j=T;
	while(j>0)
	{
		j--;
		op=0;
		int i;
		for(i=1;i<=100005;i++)
		{
			b[i]=false;
			c[i]=false;
			e[i].b=false;
			e[i].c=false;
			e[i].n=0;
		}
		workout();
		printf("%d\n",op);
		for(i=1;i<=op;i++)
		{
			if(opp[i].n==1)
				printf("%d %d\n",opp[i].n,opp[i].m1);
			else
				printf("%d %d %d\n",opp[i].n,opp[i].m1,opp[i].m2);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
