给你一个整数$$$n$$$。
让我们将 $$$s(n)$$$ 定义为连接 $$$n$$$ 次的字符串“BAN”。例如,$$$s(1)$$$ =“BAN”,$$$s(3)$$$ =“BANBANBAN”。请注意,字符串 $$$s(n)$$$ 的长度等于 $$$3n$$$。
考虑$$$s(n)$$$。您可以对 $$$s(n)$$$ 执行以下操作任意次数(可能为零):
- 选择任意两个不同的索引 $$$i$$$ 和 $$$j$$$ $$$(1 \leq i, j \leq 3n, i \ne j)$$$。
- 然后,交换$$$s(n)_i$$$和$$$s(n)_j$$$。
您希望字符串“BAN”不作为子序列出现在 $$$s(n)$$$ 中。要实现这一目标,您需要执行的最少操作次数是多少?另外,找到一个这样的最短操作序列。
如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 100)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 100)$$$。
输出
对于每个测试用例,在第一行输出 $$$m$$$ ($$$0 \le m \le 10^5$$$) — 所需的最少操作数。保证在问题约束下最多 $$$10^5$$$ 次操作中始终可以实现目标。
然后,输出 $$$m$$$ 行。这些行的第 $$$k$$$ 应包含两个整数 $$$i_k$$$、$$$j_k$$$ $$$(1\leq i_k, j_k \leq 3n, i_k \ne j_k)$$$ 表示您要在第 $$$k$$$ 操作中交换索引 $$$i_k$$$ 和 $$$j_k$$$ 处的字符。
在所有 $$$m$$$ 操作之后,“BAN”不得作为子序列出现在 $$$s(n)$$$ 中。
如果有多个可能的答案,则输出任何一个。
示例
输入 #1
2 1 2
输出 #1
1 1 2 1 2 6
注意
在第一个测试用例中,$$$s(1) = $$$ "BAN",我们可以交换$$$s(1)_1$$$和$$$s(1)_2$$$,将$$$s(1)$$$转换为“ABN”,其中不包含“BAN”作为子序列。
在第二个测试用例中,$$$s(2) = $$$ "BANBAN",我们可以交换$$$s(2)_2$$$和$$$s(2)_6$$$,将$$$s(2)$$$转换为“BNNBAA”,其中不包含“BAN”作为子序列。