平面上有 $2n$ 个不同的点。点 $i$ 的坐标为 $(x_i, y_i)$。

如果两个点 $i$ 和 $j$ 满足 $x_i = x_j$ 或 $y_i = y_j$，则称它们为“友好对”。

请将这 $2n$ 个点两两配对，形成 $n$ 个点对，使得每个点恰好属于一个点对。你需要最小化这 $n$ 个点对中友好对的数量。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

每个测试用例的描述如下： 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。 接下来的 $2n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个点的坐标 ($-10^9 \le x_i, y_i \le 10^9$)。所有点互不相同。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，首先输出一个非负整数 $k$，表示友好对的最小可能数量。 接下来的 $n$ 行中，每行输出两个整数 $a_i$ 和 $b_i$，表示由点 $a_i$ 和 $b_i$ 组成的点对 ($1 \le a_i, b_i \le 2n; a_i \neq b_i$)。

$1$ 到 $2n$ 之间的每个整数必须在 $a_i$ 和 $b_i$ 中恰好出现一次。满足点 $a_i$ 和 $b_i$ 为友好对的索引 $i$ 的数量必须等于 $k$。

样例

样例输入 1

3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3

样例输出 1

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