#include <stdio.h>
#include <algorithm>
#include <set>
#include <string.h>
#include <deque>
#include <vector>
// #define int long long
int read()
{
    int x=0,f=1,c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)x=x*10+c-48,c=getchar();
    return x*f;
}
int re1d()
{
    int c=getchar();
    while(c<48||c>57)c=getchar();
    return c-48;
}
std::deque<int>q[605];
int a[2000005],pos[605],neg[605];
int cc[605];
int rem[605];
struct oh{
    int a,b,c;
};
std::vector<oh>ou;
void p1(int x)
{
    // printf("%d\n",x);
    oh a;a.a=1;a.b=x;
    ou.push_back(a);
}
void p2(int x,int y)
{
    // printf("%d %d\n",x,y);
    oh a;a.a=2;a.b=x;a.c=y;
    ou.push_back(a);
}

signed main()
{
    freopen("meow.in","r",stdin);
    freopen("meow.out","w",stdout);
    int T=read();
    for(int tt=1;tt<=T;tt++)
    {
        int n=read(),m=read(),k=read();
        for(int i=1;i<=m;i++)a[i]=read();
        std::set<int>f,e,s;
        for(int i=1;i<=n;i++)e.insert(i);
        for(int i=1;i<=m;i++)
        {
            if(pos[a[i]])
            {
                // printf("1 %d\n",pos[a[i]]);
                p1(pos[a[i]]);
                if(q[pos[a[i]]].size()==2)f.erase(pos[a[i]]),s.insert(pos[a[i]]),pos[q[pos[a[i]]].front()]=pos[a[i]];
                else s.erase(pos[a[i]]),e.insert(pos[a[i]]);
                q[pos[a[i]]].pop_back();
                pos[a[i]]=neg[a[i]]=0;

            }
            else if(e.size()&&neg[a[i]])
            {
                int u=*e.begin();
                // printf("1 %d\n",u);
                p1(u);
                p2(u,neg[a[i]]);
                // printf("2 %d %d\n",u,neg[a[i]]);
                if(q[neg[a[i]]].size()==2)f.erase(neg[a[i]]),s.insert(neg[a[i]]),neg[q[neg[a[i]]].back()]=neg[a[i]];
                else s.erase(neg[a[i]]),e.insert(neg[a[i]]);
                q[neg[a[i]]].pop_front();
                pos[a[i]]=neg[a[i]]=0;
            }
            else if(e.size()>1)
            {
                int u=*e.begin();
                e.erase(u);
                s.insert(u);
                q[u].push_back(a[i]);
                // printf("1 %d\n",u);
                p1(u);
                pos[a[i]]=neg[a[i]]=u;
            }
            else if(s.size())
            {
                int u=*s.begin();s.erase(u);f.insert(u);
                // printf("1 %d\n",u);
                p1(u);
                q[u].push_back(a[i]);
                pos[q[u].front()]=0;
                pos[a[i]]=u;
            }
            else
            {
                memset(cc,0,sizeof(cc));
                int j;
                for(j=i+1;j<=m;j++)
                {
                    if(neg[a[j]])break;
                    else cc[a[j]]^=1;
                }
                int u=neg[a[j]],x=q[u].front(),y=q[u].back();
                for(int i=1;i<=k;i++)rem[i]=pos[i];
                if(cc[y])
                {
                    // printf("aaaaaa");fflush(stdout);
                    int v=*e.begin();e.erase(v);s.insert(v);
                    q[v].push_back(a[i]);
                    p1(v);
                    for(int k=i+1;k<j;k++)
                    {
                        p1(rem[a[k]]);
                        if(q[a[k]].size()==2)
                        {
                            f.erase(pos[a[k]]);
                            s.insert(pos[a[k]]);
                            pos[q[pos[a[k]]].front()]=pos[a[k]];
                            q[pos[a[k]]].pop_back();
                            pos[a[k]]=0;
                        }
                        else
                        {
                            pos[q[rem[a[k]]].back()]=0;
                            pos[a[k]]=rem[a[k]];
                            q[pos[a[k]]].push_back(a[k]);
                            f.insert(pos[a[k]]);
                            s.erase(pos[a[k]]);
                        }
                    }
                    i=j-1;


                }
                else
                {
                    // printf("nnnnnnn\n");fflush(stdout);
                    int v=*e.begin();
                    // printf("v=%d\n",v);fflush(stdout);
                    p1(u);q[u].push_back(a[i]);
                    q[u].pop_front();
                    for(int k=i+1;k<j;k++)
                    {
                        if(a[k]==y)
                        {
                            p1(v);
                            continue;
                        }
                        p1(rem[a[k]]);
                        if(q[a[k]].size()==2)
                        {
                            f.erase(pos[a[k]]);
                            s.insert(pos[a[k]]);
                            pos[q[pos[a[k]]].front()]=pos[a[k]];
                            q[pos[a[k]]].pop_back();
                            pos[a[k]]=0;
                        }
                        else
                        {
                            pos[q[rem[a[k]]].back()]=0;
                            pos[a[k]]=rem[a[k]];
                            q[pos[a[k]]].push_back(a[k]);
                            f.insert(pos[a[k]]);
                            s.erase(pos[a[k]]);
                        }
                    }
                    p1(v);
                    p2(u,v);
                    pos[x]=neg[x]=0;
                    pos[y]=0;
                    neg[y]=u;
                    pos[a[i]]=u;
                    neg[a[i]]=0;
                    i=j;
                }
                // for(int j=1;j<)
                // break;
            }
            // for(auto x:e)printf("e%d,",x);puts("");
        }
        printf("%d\n",(int)ou.size());
        for(int i=0;i<ou.size();i++)
        {
            if(ou[i].a==1)printf("%d %d\n",ou[i].a,ou[i].b);
            else printf("%d %d %d\n",ou[i].a,ou[i].b,ou[i].c);
        }
        ou.clear();
    }
}