#include<iostream>
#include<deque>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
std::deque<int> sta[500];
std::vector<std::pair<int, int>> ans;
std::set<int> siz[4];
int T, n, k, m, vis[1003], t[500], a[1000006];
int nxt[1003], f[1000006], cnt;
int has(int i, int x) {
	for (int _ : sta[i]) if (_ == x) return 1;
	return 0;
}
int main() {
	freopen("meow.in", "r", stdin);
	freopen("meow.out", "w", stdout);
	std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
	std::cin >> T;
	while (T--) {
		std::cin >> n >> m >> k;
		if (k == n * 2 - 2) {
			for (int i = 1; i <= n; i++) t[i] = 0;
			int j = 1;
			for (int i = 1; i <= m; i++) {
				int x; std::cin >> x;
				if (!vis[x]) {
					if (t[j] == 2) j++;
					vis[x] = j, t[j]++;
				}
				if (has(vis[x], x)) {
					if (sta[vis[x]][0] != x) {
						ans.emplace_back(1, vis[x]);
						sta[vis[x]].pop_back();
					} else {
						ans.emplace_back(1, n);
						ans.emplace_back(0, vis[x]);
						sta[vis[x]].pop_front();
					}
				} else {
					ans.emplace_back(1, vis[x]);
					sta[vis[x]].push_back(x);
				}
			}
			std::cout << ans.size() << '\n';
			for (auto p : ans) {
				int x = p.first, y = p.second;
				if (x) std::cout << "1 " << y << '\n';
				else std::cout << "2 " << n << " " << y << '\n';
			}
		} else {
			for (int i = 1; i <= m; i++) std::cin >> a[i];
			for (int i = 1; i < n; i++) siz[sta[i].size()].emplace(i);
			int spec = 0, cnt = 0, j = 0;
			for (int i = 1; i <= m; i++) {
				if (!vis[a[i]]) {
					if (t[j] == 2) j++;
					vis[a[i]] = j, t[j]++;
					if (j == n) spec = a[i], vis[a[i]] = 0;
				}
				if (a[i] == spec) {
					if (vis[a[i]]) {
						ans.emplace_back(1, vis[a[i]]);
						siz[sta[vis[a[i]]].size()].erase(vis[a[i]]);
						sta[vis[a[i]]].pop_back(), vis[a[i]] = 0;
						siz[sta[vis[a[i]]].size()].emplace(vis[a[i]]);
					} else {
						if (siz[0].size()) {
							int t = *siz[0].begin();
							vis[a[i]] = t;
							siz[sta[vis[a[i]]].size()].erase(vis[a[i]]);
							ans.emplace_back(1, vis[a[i]]);
							sta[vis[a[i]]].push_back(a[i]);
							siz[sta[vis[a[i]]].size()].emplace(vis[a[i]]);
						} else if (siz[1].size()) {
							int t = *siz[1].begin();
							vis[a[i]] = t;
							siz[sta[vis[a[i]]].size()].erase(vis[a[i]]);
							ans.emplace_back(1, vis[a[i]]);
							sta[vis[a[i]]].push_back(a[i]);
							siz[sta[vis[a[i]]].size()].emplace(vis[a[i]]);
						} else {
							int t = *siz[2].rbegin();
							vis[a[i]] = t;
							siz[sta[vis[a[i]]].size()].erase(vis[a[i]]);
							ans.emplace_back(1, vis[a[i]]);
							sta[vis[a[i]]].push_back(a[i]);
							siz[sta[vis[a[i]]].size()].emplace(vis[a[i]]);
						}
					}
				} else {
					int x = a[i];
					if (has(vis[x], x)) {
						if (sta[vis[x]][0] != x) {
							ans.emplace_back(1, vis[x]);
							sta[vis[x]].pop_back();
						} else {
							ans.emplace_back(1, n);
							ans.emplace_back(0, vis[x]);
							sta[vis[x]].pop_front();
						}
					} else {
						ans.emplace_back(1, vis[x]);
						sta[vis[x]].push_back(x);
					}
				}
			}
			std::cout << ans.size() << '\n';
			for (auto p : ans) {
				int x = p.first, y = p.second;
				if (x) std::cout << "1 " << y << '\n';
				else std::cout << "2 " << n << " " << y << '\n';
			}
		}
	}
}
