你在无限大的棋盘上有 $n$ 个车。第 $i$ 个车位于单元格 $(r_i, c_i)$。

在一次移动中，你可以将任何一个车移动到同一行或同一列的任何单元格。换句话说，在一次移动中，你可以选择任意一个 $i$，然后将 $r_i$ 替换为任何其他整数，或者将 $c_i$ 替换为任何其他整数。你不能将车移动到已有其他车的单元格上。

如果四个不同的车 $a, b, c, d$ 能够构成一个矩形的四个顶点，则称它们构成了一个“优美形状”。换句话说，如果存在整数 $x_1, x_2, y_1, y_2$（其中 $x_1 \neq x_2$ 且 $y_1 \neq y_2$），使得单元格集合 $\{(r_a, c_a), (r_b, c_b), (r_c, c_c), (r_d, c_d)\}$ 等于集合 $\{(x_1, y_1), (x_1, y_2), (x_2, y_1), (x_2, y_2)\}$，则称这四个车构成了一个优美形状。

例如，下图中白色的车构成了一个优美形状。

你的目标是找到能够得到一个优美形状所需的最少移动次数。 换句话说，你需要找到最少的移动次数，使得移动后能够找到一个四个顶点上都有车的矩形。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 25\,000$)：测试用例的数量。 接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($4 \le n \le 100\,000$)。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $r_i, c_i$ ($1 \le r_i, c_i \le 10^9$)。 对于每一对 $i, j$（$i \neq j$），满足 $r_i \neq r_j$ 或 $c_i \neq c_j$。 所有测试用例的 $n$ 之和不超过 $100\,000$。

输出格式

对于每个测试用例，输出一个整数：为了使给定的车中至少出现一个优美形状，所需的最少移动次数。

子任务

样例

输入 1

5
4
4 4
1 1
2 2
3 3
4
4 4
4 1
1 4
2 2
6
3 2
2 1
1 2
3 3
3 4
3 1
5
1 1
1 2
1 3
1 4
5 5
4
1000000000 1000000000
1000000000 1
2 2
1000000000 999999999

输出 1

4
2
1
3
3

说明

第一个测试用例的一种可能的最优解：

第二个测试用例的一种可能的最优解：