#include<bits/stdc++.h>
using namespace std;

struct node{
	int Id,val;
	bool operator < (const node & A)const{
		return val>A.val;
	}
};

priority_queue<node>Q;

int T,n,m,k,a[2000010],L[610],vis[610],Del[610],Stlen[610],Down[610],Size,re[610],op;
queue<int>S;
vector<int>St[610];
vector<int>:: iterator it;

void clear(){
	op=0,Size=0;
	for(int i=0; i<=n; i++) St[i].clear();
	while(!S.empty())S.pop();
	while(!Q.empty())Q.pop();
//	memset(a,0,sizeof(a));
	memset(L,0,sizeof(L));
	memset(vis,0,sizeof(vis));
	memset(Del,0,sizeof(Del));
	memset(Stlen,0,sizeof(Stlen));
	memset(Down,0,sizeof(Down));
	memset(re,0,sizeof(re));
}

void del1(int x,int y){
	op++;
//	printf("2 %d %d\n",x,y);
	Down[St[x][0]]=Down[St[y][0]]=0;
	Stlen[x]--;
	Stlen[y]--;
	St[x].erase(St[x].begin());
	St[y].erase(St[y].begin());
	if(Stlen[x]>0){
		if(Down[St[x][0]]) del1(x,Down[St[x][0]]);
		else Down[St[x][0]]=x;
	}
	if(Stlen[y]>0){
		if(Down[St[y][0]]) del1(y,Down[St[y][0]]);
		else Down[St[y][0]]=y;
	}
}

void del2(int x,int y){
	op++;
	printf("2 %d %d\n",x,y);
	Down[St[x][0]]=Down[St[y][0]]=0;
	Stlen[x]--;
	Stlen[y]--;
	St[x].erase(St[x].begin());
	St[y].erase(St[y].begin());
	if(Stlen[x]>0){
		if(Down[St[x][0]]) del2(x,Down[St[x][0]]);
		else Down[St[x][0]]=x;
	}
	if(Stlen[y]>0){
		if(Down[St[y][0]]) del2(y,Down[St[y][0]]);
		else Down[St[y][0]]=y;
	}
}

void prepare(){
	op=0;
	Size=n;
	    for(int i=2; i<=k+1; i++){
	    	vis[a[i]]=i;
		}
		for(int i=1; i<=n; i++) Q.push((node){i,0}),S.push(i),Stlen[i]=0;
		for(int i=1; i<=m; i++){
			if(L[a[i]]>0){
				op+=1;
				//printf("1 %d\n",L[a[i]]);
				if(re[a[i]]>0){
					Q.push((node){re[a[i]],Stlen[re[a[i]]]-1});
					re[a[i]]=0;
				}
				it=St[L[a[i]]].end();
				--it;
				Stlen[L[a[i]]]--;
				if(Stlen[L[a[i]]]==0){
					Down[a[i]]=0;
					S.push(L[a[i]]);
					Size++;
				}
				else L[St[L[a[i]]][Stlen[L[a[i]]]-1]]=L[a[i]];
				St[L[a[i]]].erase(it);
				L[a[i]]=0;
			}else if(Size>0&&Down[a[i]]>0){
				op+=2;
			//	printf("1 %d\n",S.front());
			//	printf("2 %d %d\n",S.front(),Down[a[i]]);
				St[Down[a[i]]].erase(St[Down[a[i]]].begin());
				Stlen[Down[a[i]]]--;
				if(Stlen[Down[a[i]]]==0){
					S.push(L[a[i]]);
					Size++;
				}
				else{
					if(Down[St[Down[a[i]]][0]]){
						del1(Down[St[Down[a[i]]][0]],Down[a[i]]);
					}
				    //Down[St[Down[a[i]]][0]]=Down[a[i]];
				}
				Down[a[i]]=0;
			}else{
				if(Size>0){
					op+=1;
					L[a[i]]=S.front();
					Down[a[i]]=S.front();
				//	printf("1 %d\n",S.front());
					St[S.front()].push_back(a[i]);
					Stlen[S.front()]++;
					Size--;
					S.pop();
				}else{
				    while(vis[St[Q.top().Id][St[Q.top().Id].size()-1]]){
					    re[St[Q.top().Id][St[Q.top().Id].size()-1]]=Q.top().Id;
					    Q.pop();
				    }
				    op+=1;
				   // printf("1 %d\n",Q.top());
				    //c//out<<Q.top().Id<<" "<<" "<<Stlen[Q.top().Id]-1<<" "<<St[Q.top().Id].size()<<" "<<St[Q.top().Id][Stlen[Q.top().Id]-1]<<endl;
				    L[St[Q.top().Id][Stlen[Q.top().Id]-1]]=0;
				    L[a[i]]=Q.top().Id;
				    St[Q.top().Id].push_back(a[i]);
				    Stlen[Q.top().Id]++;
				}
			}
			vis[a[i+1]]=0;
			if(i+1+k<=n)vis[a[i+1+k]]=1;
		}
	printf("%d\n",op);
	return ;
}

int main(){
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		clear();
		op=0;
		scanf("%d %d %d",&n,&m,&k);
	    for(int i=1; i<=m; i++) scanf("%d",&a[i]);
	    prepare();
	    clear();
	    Size=n;
	    for(int i=2; i<=k+1; i++){
	    	vis[a[i]]=i;
		}
		for(int i=1; i<=n; i++) Q.push((node){i,0}),S.push(i),Stlen[i]=0;
		for(int i=1; i<=m; i++){
			if(L[a[i]]>0){
				op+=1;
				printf("1 %d\n",L[a[i]]);
				if(re[a[i]]>0){
					Q.push((node){re[a[i]],Stlen[re[a[i]]]-1});
					re[a[i]]=0;
				}
				it=St[L[a[i]]].end();
				--it;
				Stlen[L[a[i]]]--;
				if(Stlen[L[a[i]]]==0){
					Down[a[i]]=0;
					S.push(L[a[i]]);
					Size++;
				}
				else L[St[L[a[i]]][Stlen[L[a[i]]]-1]]=L[a[i]];
				St[L[a[i]]].erase(it);
				L[a[i]]=0;//cout<<"yes";
			}else if(Size>0&&Down[a[i]]>0){
				op+=2;
				printf("1 %d\n",S.front());
				printf("2 %d %d\n",S.front(),Down[a[i]]);
				St[Down[a[i]]].erase(St[Down[a[i]]].begin());
				Stlen[Down[a[i]]]--;
				if(Stlen[Down[a[i]]]==0){
					S.push(L[a[i]]);
					Size++;
				}
				else{
					if(Down[St[Down[a[i]]][0]]){
						del2(Down[St[Down[a[i]]][0]],Down[a[i]]);
					}
				    //Down[St[Down[a[i]]][0]]=Down[a[i]];
				}
				Down[a[i]]=0;//cout<<"yes";
			}else{
				if(Size>0){
					op+=1;
					L[a[i]]=S.front();
					Down[a[i]]=S.front();
					printf("1 %d\n",S.front());
					St[S.front()].push_back(a[i]);
					Stlen[S.front()]++;
					Size--;
					S.pop();//cout<<"yes6";
				}else{
				    while(vis[St[Q.top().Id][St[Q.top().Id].size()-1]]){
					    re[St[Q.top().Id][St[Q.top().Id].size()-1]]=Q.top().Id;
					    Q.pop();
				    }
				    op+=1;
				    printf("1 %d\n",Q.top());
				    //cout<<Q.top().Id<<" "<<" "<<Stlen[Q.top().Id]-1<<" "<<St[Q.top().Id].size()<<" "<<St[Q.top().Id][Stlen[Q.top().Id]-1]<<endl;
				    L[St[Q.top().Id][Stlen[Q.top().Id]-1]]=0;
				    L[a[i]]=Q.top().Id;
				    St[Q.top().Id].push_back(a[i]);
				    Stlen[Q.top().Id]++;
				    //cout<<"yes";
				}
			}
			vis[a[i+1]]=0;
		    if(i+1+k<=n)vis[a[i+1+k]]=1;	
		}
	}
	return 0;
}