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

template<typename T>
inline void read(T &x) {
    x = 0; char ch = getchar();
    bool f = 0;
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    if (f) x = -x;
}
template<typename T>
inline void write(T x, char c) {
    if (x == 0) {
        putchar('0'), putchar(c);
        return;
    }
    static int stk[20];
    int top = 0;
    while (x) stk[++top] = x % 10, x /= 10;
    while (top) putchar('0' + stk[top--]);
    putchar(c);
}

const int N = 605, M = 4000005;
int T, n, m, k, a[M], bel[N], stk[N], top;
int op[M], x[M], y[M], tot, cur[N];
vector<int> b[N];

inline void push1(int x) {
    op[++tot] = 1;
    ::x[tot] = x;
}
inline void push2(int x, int y) {
    op[++tot] = 2;
    ::x[tot] = x, ::y[tot] = y;
}

inline int get_pos(int x) {
    return b[bel[x]][0] == x ? 1 : 2;
}
inline void popBack(int pos) {
    int x = b[pos].back();
    b[pos].pop_back();
    bel[x] = 0;
    stk[++top] = pos;
}
inline void popFront(int pos) {
    int x = b[pos][0];
    b[pos].erase(b[pos].begin());
    bel[x] = 0;
    stk[++top] = pos;
}

void solve() {
    read(n), read(m), read(k);
    for (int i = 1; i <= m; ++i) read(a[i]);
    
    if (n == 1) {
        write(m, '\n');
        for (int i = 1; i <= m; ++i) write(1, ' '), write(1, '\n');
        return;
    }

    for (int i = 1; i <= n; ++i) b[i].clear();
    for (int i = 1; i <= k; ++i) bel[i] = 0;
    top = tot = 0; 
    for (int i = 1; i < n; ++i) stk[++top] = i, stk[++top] = i;
    int empty_pos = n;
    
    for (int p = 1; p <= m; ) {
        int x = a[p];
        if (bel[x]) {
            if (get_pos(x) == 1) {
                push1(empty_pos);
                push2(bel[x], empty_pos);
                popFront(bel[x]);
            } else {
                push1(bel[x]);
                popBack(bel[x]);
            }
            ++p;
        } else if (top) {
            bel[x] = stk[top--];
            push1(bel[x]);
            b[bel[x]].push_back(x);
            ++p;
        } else {
            push1(-1);
            int tmp = tot;
            int pos = -1;
            int p1 = ++p;
            for (; p1 <= m; ++p1) {
                int y = a[p1];
                if (y == x) {
                    break;
                } else {
                    int b = bel[y];
                    if (get_pos(y) == 2) {
                        cur[b] ^= 1;
                    } else {
                        pos = b;
                        break;
                    }
                }
            }
            if (pos == -1) {
                cerr << "?\n";
                ::x[tmp] = empty_pos;
                for (int i = p; i < p1; ++i) {
                    int y = a[i], b = bel[y];
                    push1(b);
                }
                push1(empty_pos);
                for (int i = p1 - 1; i >= p; --i) {
                    int y = a[i], b = bel[y];
                    if (cur[b]) {
                        popBack(b);
                        cur[b] = 0;
                    }
                }
            } else if (cur[pos] == 1) {
                cerr << "??\n";
                ::x[tmp] = empty_pos;
                bel[x] = empty_pos;
                b[empty_pos].push_back(x);
                for (int i = p; i <= p1; ++i) {
                    int y = a[i], b = bel[y];
                    push1(b);
                }
                popBack(pos), popBack(pos);
                top -= 2;
                cur[pos] = 0;
                for (int i = p1 - 1; i >= p; --i) {
                    int y = a[i], b = bel[y];
                    if (cur[b]) {
                        popBack(b);
                        cur[b] = 0;
                    }
                }
                stk[++top] = empty_pos;
                empty_pos = pos;
            } else {
                cerr << "???\n";
                ::x[tmp] = pos;
                for (int i = p; i < p1; ++i) {
                    int y = a[i], b = bel[y];
                    push1(b == pos ? empty_pos : b);
                }
                assert(b[pos].size() == 2);
                assert(cur[pos] == 0);
                for (int i = p1 - 1; i >= p; --i) {
                    int y = a[i], b = bel[y];
                    if (cur[b]) {
                        popBack(b);
                        cur[b] = 0;
                    }
                }
                push1(empty_pos);
                push2(pos, empty_pos);
                bel[b[pos][0]] = 0;
                b[pos][0] = b[pos][1];
                b[pos][1] = x;
                bel[x] = pos;
            }
            p = p1 + 1;
        }   
    } 

    write(tot, '\n');
    for (int i = 1; i <= tot; ++i) {
        write(op[i], ' ');
        if (op[i] == 1) {
            write(x[i], '\n');
        } else {
            write(x[i], ' ');
            write(y[i], '\n');
        }
    }

    for (int i = 1; i <= n; ++i) b[i].clear();
    int j = 0;
    for (int i = 1; i <= tot; ++i) {
        if (op[i] == 1) {
            int x = a[++j];
            int pos = ::x[i];
            if (!b[pos].empty() && b[pos].back() == x) {
                b[pos].pop_back();
            } else {
                b[pos].push_back(x);
            }
        } else {
            int x = ::x[i], y = ::y[i];
            assert(!b[x].empty() && !b[y].empty());
            assert(b[x][0] == b[y][0]);
            b[x].erase(b[x].begin()), b[y].erase(b[y].begin());
        }
    }
    assert(j == m);
    for (int i = 1; i <= n; ++i) assert(b[i].empty());
}

int main() {
    freopen("meow.in", "r", stdin);
    freopen("meow.out", "w", stdout);

    read(T);
    while (T--) solve();

    return 0;
}