#include <bits/stdc++.h>

#ifndef CM_DEBUG
#undef assert
#define assert(...) ;
#endif

int read_int()
{
	int c = getchar();
	while (!std::isdigit(c))
		c = getchar();
	int x = 0;
	while (std::isdigit(c))
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}

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

	int t = read_int();
	for (int i = 0; i < t; i++)
	{
#ifdef CM_DEBUG
		// printf("Case %d\n", i);
#endif

		int n = read_int();
		int m = read_int();
		int k = read_int();
		std::vector<int> as(m);
		for (int &x: as)
			x = read_int() - 1;

		std::vector<std::vector<int>> stacks(n);
		for (auto &s: stacks)
			s.reserve(4);

		std::vector<int> vac[5];
		int vac_cnt[5] = {0, 0, 0, 0, 0};
		auto vac_erase = [&](int p) {
			vac_cnt[stacks[p].size()] -= 1;
		};
		auto vac_insert = [&](int p) {
			vac_cnt[stacks[p].size()] += 1;
			vac[stacks[p].size()].push_back(p);
		};
		auto vac_get = [&](int s) {
			assert(vac_cnt[s] > 0);
			while ((int)stacks[vac[s].back()].size() != s)
				vac[s].pop_back();
			return vac[s].back();
		};

		for (int i = 0; i < n; i++)
			vac_insert(i);
		std::shuffle(vac[0].begin(), vac[0].end(), std::mt19937(18100301));

		std::vector<std::tuple<int, int, int>> ops;
		auto as_it = as.begin();
		auto op_push = [&](int p) {
			ops.emplace_back(1, p, -1);
			int v = *as_it++;
			if (!stacks[p].empty() && stacks[p].back() == v)
			{
				vac_erase(p);
				stacks[p].pop_back();
				vac_insert(p);
			}
			else
			{
				vac_erase(p);
				stacks[p].push_back(v);
				vac_insert(p);
			}
		};
		auto op_join = [&](int px, int py) {
			ops.emplace_back(2, px, py);
			auto &sx = stacks[px], &sy = stacks[py];
			assert(!sx.empty() && !sy.empty());
			assert(sx.front() == sy.front());
			vac_erase(px);
			vac_erase(py);
			sx.erase(sx.begin());
			sy.erase(sy.begin());
			vac_insert(px);
			vac_insert(py);
		};

		std::vector<std::vector<int>> occur(k, std::vector<int>{m});
		for (int i = m - 1; i >= 0; i--)
			occur[as[i]].push_back(i);
		auto get_occur = [&](int c, int p) {
			while (occur[c].back() <= p)
				occur[c].pop_back();
			return occur[c].back();
		};

		std::vector<int> pos(k, -1);

		for (int i = 0; i < m; i++)
		{
			int c = as[i];
			int &p = pos[c];
			if (p != -1)
			{
				if (stacks[p].back() == c)
				{
					op_push(p);
					if (std::find(stacks[p].begin(), stacks[p].end(), c) == stacks[p].end())
						p = -1;
				}
				else
				{
					if (stacks[p].front() == c && vac_cnt[0] >= 1)
					{
						int hole = vac_get(0);
						op_push(hole);
						op_join(p, hole);
						p = -1;
					}
					else
					{
						op_push(p);
					}
				}
			}
			else
			{
				p = [&] {
					if (vac_cnt[1] >= 1)
						return vac_get(1);
					else if (vac_cnt[0] >= 2)
						return vac_get(0);
					else
					{
						// sticky part
						auto dest = [&](int cur) {
							int next = get_occur(as[cur], cur);
							for (int i = 0; i < n; i++)
								if (!stacks[i].empty())
								{
									assert(stacks[i].size() == 2);
									int av = stacks[i][0], bv = stacks[i][1];
									int an = get_occur(av, cur), bn = get_occur(bv, cur);
									if (an > next && bn > next)
										return i;
									if (an < next)
									{
										auto f_l = std::lower_bound(
												occur[bv].begin(), occur[bv].end(), an, std::greater<int>());
										auto f_r = occur[bv].end();
										if (std::distance(f_l, f_r) % 2 == 0)
											return i;
									}
								}
							return -1;
						}(i);

						if (dest != -1)
							return dest;
						else
							return vac_get(0);
					}
				}();

				op_push(p);
			}

			/*
			for (int i = 0; i < n; i++)
			{
				printf("stacks[%d] = {", i);
				for (int j = 0; j < (int)stacks[i].size(); j++)
				{
					if (j == 0)
						printf("%d", stacks[i][j]);
					else
						printf(", %d", stacks[i][j]);
				}
				printf("}\n");
			}
			*/
		}

		printf("%d\n", (int)ops.size());
		for (const auto &[op, px, py]: ops)
		{
			if (op == 1)
				printf("1 %d\n", px + 1);
			else
				printf("2 %d %d\n", px + 1, py + 1);
		}

		assert(as_it == as.end());
		for (int i = 0; i < n; i++)
			assert(stacks[i].empty());
	}

	return 0;
}
