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

const int N = 2e6 + 5;
const int W = 605;

inline int rd() {
	char c; int x = 0;
	do c = getchar(); while (!isdigit(c));
	do x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); while (isdigit(c));
	return x;
}

void wt(int x) {
	if (x > 9) wt(x / 10), x %= 10;
	putchar(x + 48);
}

struct ANS {
	int op__, s1__, s2__;
	ANS(int op = 0, int s1 = 0, int s2 = 0) : op__(op), s1__(s1), s2__(s2) {}
	void show() const {
		wt(op__), putchar(' ');
		if (op__ == 1) wt(s1__), putchar('\n');
		else wt(s1__), putchar(' '), wt(s2__), putchar('\n');
	}
};
vector<ANS> ans; 
inline void push(int id) {
	ans.push_back(ANS(1, id));
}
inline void merge(int id1, int id2) {
	ans.push_back(ANS(2, id1, id2));
}
int a[N];
namespace S1 {
	int pos[W], sta[W], st[W][2];
	queue<int> q;
	void Main() {
		int n, m, k;
		ans.clear();
		n = rd(), m = rd(), k = rd();
		for (int i = 1; i <= m; ++i) a[i] = rd();
			
		for (int i = 0; i < W; ++i)
			pos[i] = sta[i] = st[i][0] = st[i][1] = 0;
		while (!q.empty()) q.pop();
		for (int i = 1; i < n; ++i) q.push(i), q.push(i);
		
		for (int i = 1; i <= m; ++i) {
			int x = a[i], p = pos[x];
			if (p) {
				if (sta[x] == 0) {
					push(n), merge(p, n);
					st[p][0] = st[p][1], st[p][1] = 0;
					if (st[p][0]) sta[st[p][0]] = 0;
				} else push(p), st[p][1] = 0;
				pos[x] = 0, q.push(p);
			} else {
				p = pos[x] = q.front(), q.pop(), push(p);
				if (st[p][0]) st[p][1] = x, sta[x] = 1;
				else st[p][0] = x, sta[x] = 0;
			}
		}
		
		wt(int(ans.size())), putchar('\n');
		for (ANS & x : ans) x.show();
	}
}

namespace S2 {
	int vis[5];
	deque<int> v[3];
	void Main() {
		int n, m, k;
		ans.clear();
		n = rd(), m = rd(), k = rd();
		for (int i = 1; i <= m; ++i) a[i] = rd();
		for (int i = 1; i < 3; ++i) v[i].clear();
		
		for (int i = 1; i <= m; ++i) {
			int x = a[i];
			if (vis[x]) {
				vis[x] = 0;
				if (!v[1].empty() && v[1].back() == x) {
					push(1), v[1].pop_back(); 
					continue;
				}
				if (!v[2].empty() && v[2].back() == x) {
					push(2), v[2].pop_back();
					continue;
				}
				if (!v[1].empty() && v[1].front() == x) {
					push(2), merge(1, 2), v[1].pop_front();
					continue;
				}
				if (!v[2].empty() && v[2].front() == x) {
					push(1), merge(1, 2), v[2].pop_front();
					continue;
				}
			} else {
				vis[x] = 1;
				int cnt = v[1].size() + v[2].size();
				if (cnt < 2) {
					if (v[1].empty()) {
						push(1), v[1].push_back(x);
						continue;
					}
					if (v[2].empty()) {
						push(2), v[2].push_back(x);
						continue;
					}
				}
				int y = a[i + 1];
				if (x == y) {
					push(1), v[1].push_back(x);
					continue;
				}
				if (!v[1].empty() && y == v[1].back()) {
					push(2), v[2].push_back(x);
					continue;
				}
				if (!v[2].empty() && y == v[2].back()) {
					push(1), v[1].push_back(x);
					continue;
				}
				if (!v[1].empty() && y == v[1].front()) {
					push(1), v[1].push_back(x);
					continue;
				}
				if (!v[2].empty() && y == v[2].front()) {
					push(2), v[2].push_back(x);
					continue;
				}
			}
		}
		
		wt(int(ans.size())), putchar('\n');
		for (ANS & x : ans) x.show();
	}
}

namespace S3 {
	int pos[6], v[5][5], c[5];
	int ban;
	
	inline void push(int id, int val) {
		ans.push_back(ANS(1, id));
		if (v[id][c[id]] != val)
			v[id][++c[id]] = val, pos[val] = id;
		else v[id][c[id]--] = 0, pos[val] = 0;
	} 
	inline void merge(int id1, int id2) {
		ans.push_back(ANS(2, id1, id2));
		if (v[id1][1] != v[id2][1]) return;
		pos[v[id1][1]] = pos[v[id2][1]] = 0;
		for (int i = 1; i < c[id1]; ++i)
			v[id1][i] = v[id1][i + 1];
		v[id1][c[id1]--] = 0;
		for (int i = 1; i < c[id2]; ++i)
			v[id2][i] = v[id2][i + 1];
		v[id2][c[id2]--] = 0;			
	}
	
	inline void solve(int A, int B, int C, int x, int y, int z) {
		if (x == y) {
			push(C, x);
			return;
		}
		if (v[B][1] == y || v[B][2] == y) swap(A, B);
		if (v[A][1] == y) {
			push(A, x);
			return;
		}
		if (v[A][2] == y) {
			if (v[A][1] == z) {
				push(C, x);
				return;
			}
			if (v[B][1] == z) {
				push(B, x);
				return;
			}
			if (v[B][2] == z) {
				push(C, x);
				return;
			}
			push(C, x);
		}
	}
	
	queue<int> sss[10];
	int zzz[N];
	int st[N], b[N];
	void Main() {
		int n, m, k;
		ans.clear();
		n = rd(), m = rd(), k = rd();
		for (int i = 1; i <= k; ++i) pos[i] = 0;
		for (int i = 1; i <= m; ++i) 
			a[i] = rd(), zzz[i] = 0;
		
		int top = 0;
		for (int i = 1; i <= m; ++i) 
			if (top && a[st[top]] == a[i])
				zzz[st[top]] = zzz[i] = 1, top--;
			else st[++top] = i;
		
		for (int i = 1; i <= top; ++i) sss[a[st[i]]].push(i), b[st[i]] = i;
		for (int i = 1; i <= 5; ++i)
			for (int j = 0; j < 5; ++j)
				v[i][j] = 0;
		
		ban = 0;
		for (int i = 1; i <= m; ++i) {
			if (zzz[i]) {
				::push(zzz[i]);
				continue;
			}
			int x = a[i], cnt = c[1] + c[2] + c[3];
			sss[x].pop();
			if (!pos[x] && cnt <= 3) {
				if (c[1] == 1 && c[2] == 1 && c[3] == 1) {
					int xx = v[1][1], yy = v[2][1], zz = v[3][1];
					int mx = min(sss[xx].front(), min(sss[yy].front(), sss[zz].front()));
					if (mx == sss[xx].front()) ban = 1;
					else if (mx == sss[yy].front()) ban = 2;
					else if (mx == sss[zz].front()) ban = 3;
				}
				int bo = 0;
				for (int j = 1; !bo && j <= 3; ++j)
					if (c[j] == 1 && ban != j)
						push(j, x), bo = 1;
				if (bo) continue;
				
				for (int j = 1; j <= 3; ++j)
					if (c[j] < 2 && ban != j) {
						push(j, x);
						break;
					}
				continue;
			}
			if (!pos[x] && cnt == 4) {
				if (c[1] == 2 && c[2] == 2) {
					solve(1, 2, 3, x, a[st[b[i] + 1]], a[st[b[i] + 2]]);
					continue;
				}
				if (c[2] == 2 && c[3] == 2) {
					solve(2, 3, 1, x, a[st[b[i] + 1]], a[st[b[i] + 2]]);
					continue;
				}
				if (c[1] == 2 && c[3] == 2) {
					solve(1, 3, 2, x, a[st[b[i] + 1]], a[st[b[i] + 2]]);
					continue;
				}
				for (int j = 1; j <= n; ++j)
					if (c[j] < 2 && ban != j) {
						push(j, x);
						break;
					} 
				continue;
			}
			if (pos[x]) {
				if (v[1][c[1]] == x) {
					push(1, x);
					continue;
				} 
				if (v[2][c[2]] == x) {
					push(2, x);
					continue;
				}
				if (v[3][c[3]] == x) {
					push(3, x);
					continue;
				}
				int id = 0;
				for (int j = 1; !id && j <= 3; ++j)
					if (!c[j]) push(j, x), id = j;
				if (id)
					for (int j = 1; j <= 3; ++j)
						if (j != id && v[j][1] == x) {
							merge(id, j);
							break;
						}
			}
		}
		printf("%d\n", int(ans.size()));
		for (ANS & x : ans) x.show();
		for (int i = 1; i <= m; ++i) b[i] = 0;
	}
}

int main() {
	freopen("meow.in", "r", stdin);
	freopen("meow.out", "w", stdout);
	int T = rd();
	
	for (int i = 1; i <= T; ++i) {
		int x = T % 10;
		if (x == 1) S1::Main();	
		else if (x == 2) S2::Main();
		else S3::Main();
	}
	return 0;
}