给定一个大小为 $N$ 的排列。你想要将其排序。在一次操作中，你可以交换数组中第 $i$ 个和第 $j$ 个元素（$1 \le i, j \le N$），代价为 $i \& j$（$i$ 与 $j$ 的按位与）。排序该排列的总代价是所有操作代价之和。你最多只能进行 $3N$ 次操作。请输出排序该排列的最小代价，并输出一组能以最小代价完成排序的交换操作序列。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^4$）。每个测试用例的第一行包含一个整数 $N$（$1 \le N \le 10^4$），表示排列的长度。下一行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$（$1 \le a_i \le N$）。

保证所有测试用例中 $N$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，第一行输出排序数组的最小代价。下一行输出所需的操作次数。接下来的每一行包含两个整数，描述被交换的下标。详情请参考样例。

样例

样例输入 1

1
4
3 1 4 2

样例输出 1

0
3
1 4
4 3
1 2

说明

大小为 $N$ 的排列是一个大小为 $N$ 的数组，其中从 $1$ 到 $N$ 的每个数字恰好出现一次。