题目描述

一座城市中有 $n$ 个车站，编号为 $0\sim n-1$。任意两个不同的车站 $i,j$ 之间都有一条双向高铁线路，花费为 $w_{i\oplus j}$，其中 $\oplus$ 表示按位异或。

你需要保留若干条线路，使所有车站互相可达，并使保留线路的花费总和最小。输出一种最优方案。

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每组数据，第一行一个整数 $n$，表示车站个数。

第二行包含 $2^k$ 个整数 $w_0,w_1,\ldots,w_{2^k-1}$，其中 $k$ 为满足 $n\le2^k$ 的最小非负整数。

当 $n$ 本身为二的幂时，读入 $n$ 个权值；$n=1$ 时读入一个权值 $w_0$。

输出格式

对于每组数据，先输出一个整数 $s$，表示保留的线路数量。接下来 $s$ 行，每行两个整数 $x,y$，满足 $0\le x\lt y\lt n$，表示保留连接这两个车站的线路。

输出的线路必须使所有车站连通，且总花费最小。如果有多种最优方案，输出任意一种即可。

由于所有权值为正，最优方案恰好包含 $n-1$ 条线路。$n=1$ 时输出 $0$。

输入/输出样例 #1

1
3
1 1 1 1

2
0 1
1 2

输入/输出样例 #2

1
4
1 1 2 2

3
0 1
1 2
2 3

数据范围与提示

对于所有数据，$1\le T\le10^4$，$1\le n\le2^{19}$，$1\le\sum n\le2^{20}$，$1\le w_i\le10^9$。

本题采用子任务捆绑计分，只有通过一个子任务的全部测试点才能获得该子任务的分数，总分为 $100$ 分。

$$ \begin{array}{|c|c|c|} \hline \text{子任务编号} & \text{分值} & \text{额外限制} \\ \hline 1 & 5 & n\le5 \\ \hline 2 & 10 & n\le10^3,\ \sum n\le10^3 \\ \hline 3 & 20 & n\text{ 是 }2\text{ 的幂} \\ \hline 4 & 10 & w\text{ 数组在数据范围内随机生成} \\ \hline 5 & 15 & w_i\le5 \\ \hline 6 & 40 & \text{无额外限制} \\ \hline \end{array} $$

样例 1 的方案费用为 $w_1+w_3=2$，样例 2 的方案费用为 $w_1+w_3+w_1=4$。