Let's reinterpret the problem as a sorting problem. Why? The question is that we would like to find a sequence of "simple permutations" $$$q$$$, where the product of each permutation in order results in the permutation from the input. The thing is, though, that "simple permutation" is essentially just a permutation with cycles of length 2 at most. Therefore, if we have a "simple permutation" denoted as $$$q$$$, then effectively $$$q = q^{-1}$$$, and therefore $$$q \circ q = q \circ q^{-1} = I$$$. Therefore, if we have $$$k$$$ "simple permutations" denoted as $$$q_1 , \ldots , q_k$$$, and $$$p = q_1 \circ \ldots \circ q_k$$$, then $$$p \circ q_k \circ \ldots \circ q_1$$$, and therefore we can simply find a sequence of "simple permutations", that "sort" the provided permutation, and then just reverse the order.

Now, here's my approach of finding the sequence of "simple permutations" that "sort" the provided permutation. I will prove that we will only need $$$O(\log M)$$$ "simple permutations" to sort the provided permutation. ($$$M$$$ here denotes the length of the longest cycle in the permutation.) This can be done through constructive proof, by finding a way to reduce a cycle of length $$$M$$$ into one of length $$$\lceil {\frac{M}{2}} \rceil$$$.

I found that, to do this, we can construct a "simple permutation" that swaps the odd-index elements and the even-index elements in one cycle. If the cycle length is odd, we leave the one leftover element where it was. Here is an example, let's say we have a permutation of length 8, having a cycle length of 8. Initially, the permutation is as follows: $$$p=[8,1,2,3,4,5,6,7]$$$. Now, we make a "simple permutation" that swaps the odd-index elements and the even-length elements. This permutation will be: $$$[2,1,4,3,6,5,8,7]$$$. Now the product of $$$p$$$ and this new permutation would be $$$[1,8,3,2,5,4,7,6]$$$. We can see that the permutation after this step has four self-loops (1,3,5,7), and one cycle of length 4 (8,2,4,6). This method guarantees that the maximal cycle length will be reduced from $$$M$$$ to $$$\lceil {\frac{M}{2}} \rceil$$$ in one step.

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
using namespace std;
using ll=long long;

template<class T>
vector<vector<T>> decomp(vector<T>&vec)
{
	bool visit[size(vec)];
	for(bool&b:visit)b=0;
	function<void(vector<T>&,int)>
	dfs=[&](vector<T>&res,int idx)->void
	{
		if(visit[idx])return;
		res.push_back(vec[idx]);
		visit[idx]=1;
		dfs(res,vec[idx]);
	};
	
	for(T&i:vec)i--;
	
	vector<vector<T>> ans;
	for(int i=0;i<size(vec);i++)
	{
		vector<T>tmp;
		if(!visit[i])
		{
			dfs(tmp,i);
			for(int&i:tmp)i++;
			ans.push_back(tmp);
		}
	}
	return ans;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int q;cin>>q;
	while(q--)
	{
		int n;cin>>n;
		vector<int>v(n);
		for(int&i:v)cin>>i;
		vector<vector<int>>ans;
		while(!is_sorted(begin(v),end(v)))
		{
			vector<int>conv(n),vcp=v;
			auto dc=decomp(v);
			for(auto&vv:dc)
			{
				int sz=size(vv);
				for(int i=0;i<sz-(sz&1);i++)
				{
					conv[vv[i]-1]=vv[i^1];
				}
				if(sz&1)conv[vv[sz-1]-1]=vv[sz-1];
			}
			for(int i=0;i<n;i++)
			v[i]=vcp[conv[i]-1];
			ans.emplace_back(conv);
		}
		
		reverse(begin(ans),end(ans));
		
		cout<<size(ans)<<"\n";
		for(auto&v:ans)
		{
			for(int&i:v)cout<<i<<" ";
			cout<<"\n";
		}
	}
}