#include<bits/stdc++.h>
using namespace std;
int n,m,_,i,j,k,a[2000001],top[1001],botton[1001];
set<int>p[5];
deque<int>v[500];
vector<pair<int,int>>ans;
int main(){
    freopen("meow.in","r",stdin);
    freopen("meow.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>_;
    while(_--){
        cin>>n>>m>>k;
        for(i=1;i<=m;i++)cin>>a[i];
        p[0].clear();p[1].clear();p[2].clear();
        ans.clear();
        for(i=1;i<=k;i++)top[i]=botton[i]=0;
        for(i=1;i<=n;i++)v[i].clear(),p[0].insert(i);
        for(i=1;i<=m;i++){
            if(top[a[i]]){
                int x=top[a[i]];
                ans.push_back({-1,x});
                p[v[x].size()].erase(x);
                v[x].pop_back();
                p[v[x].size()].insert(x);
                top[a[i]]=0;
                continue;
            }
            if(botton[a[i]]){
                int x=botton[a[i]],y=*p[0].begin();
                ans.push_back({-1,y});
                ans.push_back({x,y});
                p[v[x].size()].erase(x);
                v[x].pop_front();
                p[v[x].size()].insert(x);
                botton[a[i]]=0;
                if(!v[x].empty()){
                    top[v[x][0]]=0;
                    botton[v[x][0]]=x;
                }
                continue;
            }
            if(!p[1].empty()){
                int x=*p[1].begin();
                ans.push_back({-1,x});
                v[x].push_back(a[i]);
                top[a[i]]=x;
                p[2].insert(x);
                p[1].erase(x);
                continue;
            }
            if(p[0].size()>1){
                int x=*p[0].begin();
                ans.push_back({-1,x});
                v[x].push_back(a[i]);
                botton[a[i]]=x;
                p[1].insert(x);
                p[0].erase(x);
                continue;
            }
            for(k=i+1;k<=m;k++)if(a[k]==a[i])break;
            for(j=i+1;j<k;j++)if(botton[a[j]])break;
            if(j==k){
                int x=*p[0].begin();
                ans.push_back({-1,x});
                for(j=i+1;j<k;j++){
                    if(top[a[j]]){
                        int x=top[a[j]];
                        ans.push_back({-1,x});
                        p[v[x].size()].erase(x);
                        v[x].pop_back();
                        p[v[x].size()].insert(x);
                        top[a[j]]=0;
                        continue;
                    }else{
                        int x=*p[1].begin();
                        ans.push_back({-1,x});
                        top[a[j]]=x;
                        v[x].push_back(a[j]);
                        p[2].insert(x);
                        p[1].erase(x);
                        continue;
                    }
                }
                ans.push_back({-1,x});
                i=k;
            }else{
                int x=*p[0].begin(),y=botton[a[j]],w=0,c=0;
                for(k=i+1;k<j;k++)if(top[a[k]]==y)w++,c=a[k];
                if(w&1){
                    ans.push_back({-1,x});
                    for(k=i+1;k<j;k++){
                        if(a[k]==c)ans.push_back({-1,top[c]});
                        else if(top[a[k]]){
                            int x=top[a[k]];
                            ans.push_back({-1,x});
                            p[v[x].size()].erase(x);
                            v[x].pop_back();
                            p[v[x].size()].insert(x);
                            top[a[k]]=0;
                            continue;
                        }else{
                            int x=*p[1].begin();
                            ans.push_back({-1,x});
                            v[x].push_back(a[k]);
                            top[a[k]]=x;
                            p[2].insert(x);
                            p[1].erase(x);
                            continue;
                        }
                    }
                    top[c]=0;
                    v[y].pop_back();
                    p[0].erase(x);p[1].insert(x);
                    v[x].push_back(a[i]);
                    botton[a[i]]=x;
                    ans.push_back({-1,y});
                    p[1].erase(y);p[0].insert(y);
                    botton[a[j]]=0;
                    v[y].pop_back();
                    i=j;
                }else{
                    ans.push_back({-1,y});
                    for(k=i+1;k<j;k++){
                        if(top[a[k]]==y)ans.push_back({-1,y});
                        else if(top[a[k]]){
                            int x=top[a[k]];
                            ans.push_back({-1,x});
                            p[v[x].size()].erase(x);
                            v[x].pop_back();
                            p[v[x].size()].insert(x);
                            top[a[k]]=0;
                            continue;
                        }else{
                            int x=*p[1].begin();
                            ans.push_back({-1,x});
                            v[x].push_back(a[k]);
                            top[a[k]]=x;
                            p[2].insert(x);
                            p[1].erase(x);
                            continue;
                        }
                    }
                    ans.push_back({-1,x});
                    ans.push_back({x,y});
                    v[y].push_back(a[i]);
                    botton[v[y][0]]=0;
                    top[v[y][1]]=0;
                    v[y].pop_front();
                    botton[v[y][0]]=y;top[v[y][1]]=y;
                    i=j;
                }
            }
        }
        cout<<ans.size()<<"\n";
        for(pair<int,int>i:ans)if(i.first==-1)cout<<1<<" "<<i.second<<"\n";else cout<<2<<" "<<i.first<<" "<<i.second<<"\n";
    }
}