这是一个关于排列的问题。如果你不熟悉下面用到的一些术语，请参阅示例后的说明。

如果一个排列 $p$ 的每个循环的长度都不超过 2，则称该排列是简单的。例如，排列 $2, 1, 4, 3$ 是简单的，但排列 $3, 1, 2$ 不是。

给定一个排列 $p$。你的任务是将它表示为最少数量的简单排列的乘积。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 10^5$)。接下来是各个测试用例。

接下来的 $T$ 行，每行描述一个测试用例。每个测试用例包含一个整数 $n$，即排列 $p$ 的长度 ($1 \le n \le 10^5$)，随后是 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$，即排列 $p$ 本身 ($1 \le p_i \le n$，从 $1$ 到 $n$ 的每个数字在排列中恰好出现一次)。

输入中所有排列的总长度不超过 $10^6$。

输出格式

对于每个测试用例，首先输出一行，包含一个整数 $k$，即乘积中简单排列的最小数量。接下来的 $k$ 行必须描述简单排列 $q^{(1)}, q^{(2)}, \dots, q^{(k)}$，每行一个。在这些行的第 $i$ 行，输出 $n$ 个从 $1$ 到 $n$ 的不同整数，描述排列 $q^{(i)}$。乘积 $q^{(1)} \circ q^{(2)} \circ \dots \circ q^{(k)}$ 必须等于 $p$。

如果有多种最优解，输出其中任意一个即可。

样例

样例输入 1

2
4 2 1 4 3
3 3 1 2

样例输出 1

1
2 1 4 3
2
3 2 1
1 3 2

说明

长度为 $n$ 的排列是一个包含 $n$ 个整数的序列，其中从 $1$ 到 $n$ 的每个整数恰好出现一次。

排列 $p$ 中的循环是一个由 $1$ 到 $n$ 之间的不同整数组成的序列 $i_1, i_2, \dots, i_t$，满足 $p_{i_1} = i_2, p_{i_2} = i_3, \dots, p_{i_{t-1}} = i_t$ 以及 $p_{i_t} = i_1$。数字 $t \ge 1$ 被称为循环的长度。

两个排列 $a$ 和 $b$ 的乘积 $a \circ b$ 是一个排列 $c$，使得对于每个 $i$，都有 $c_i = a_{b_i}$。例如，如果 $a = 3, 2, 1$ 且 $b = 1, 3, 2$，则它们的乘积为 $a \circ b = 3, 1, 2$。

三个或更多排列的乘积可以按任意顺序计算，例如，$a \circ b \circ c = (a \circ b) \circ c = a \circ (b \circ c)$。