题目描述

定义两个二元组 $(x_i,\ y_i), \ (x_j, \ y_j)$ 的 变异距离 $d_{i, \ j}$ 为

$$d_{i, \ j}=|x_i - x_j| \times \operatorname{min}(|y_i|, \ |y_j|) $$

给定 $n$ 个二元组，试确定 $d_{i, \ j}$ 的最大值。

输入格式

输入包含多组测试数据。

输入的第一行是一个整数 $T$，表示测试数据的组数。接下来有一个空行。每组数据的第一行为整数 $n$，表示二元组的数量，接下来 $n$ 行，每行一个二元组 $(x_i, \ y_i)$。每两组测试数据之间有一个空行。

输出格式

每组测试数据输出一个整数，表示二元组变异距离 $d_{i, \ j }$ 的最大值。

输入输出样例

2

3
-10 4
5 10
20 -2

3
-10 4
5 10
20 -2

60
60

说明/提示

子任务测试采用捆绑方式计分。

样例说明

$d_{1, \ 2}=d_{2, \ 1} = |-10 - 5| \times \operatorname{min}(|4|, \ |10|) = 15 \times 4 = 60$；

$d_{1, \ 3}=d_{3, \ 1} = |-10 - 20| \times \operatorname{min}(|4|, \ |-2|) = 30 \times 2 = 60$；

$d_{2, \ 3}=d_{3, \ 2} = |5 - 20| \times \operatorname{min}(|10|, \ |-2|) = 15 \times 2 = 30$；

故输出 $60$。

---

数据范围

• $\texttt{Subtask 1(30 pts)}$：$2 \le n \le 10^4$。
• $\texttt{Subtask 2(50 pts)}$：$2 \le n \le 10^5$。
• $\texttt{Subtask 3(20 pts)}$：$2 \le n \le 2 \times 10^6$。

对于 $100\%$ 的数据，$1 \le T \le 10$，$-10^6 \le x_i \le 10^6$，$-10^9 \le \ y_i \le 10^9$。

---

提示

最后一个子任务的输入数据量较大，建议使用较快的输入读取方式。