题目描述

在一个平面直角坐标系中画一个左下角坐标为 $(0,0)$ 并且右上角坐标为 $(w,h)$ 的一个矩形。保证矩形的四条边都与坐标轴平行。

在直线 $y=0$ 上有 $k_1$ 个点 $(x_1,0),(x_2,0),\cdots,(x_{k_1},0)$，保证 $x_1<x_2<\cdots<x_{k_1}$。

在直线 $y=h$ 上有 $k_2$ 个点 $(x_1,h),(x_2,h),\cdots,(x_{k_2},h)$，保证 $x_1<x_2<\cdots<x_{k_2}$。

在直线 $x=0$ 上有 $k_3$ 个点 $(0,y_1),(0,y_2),\cdots,(0,y_{k_3})$，保证 $y_1<y_2<\cdots<y_{k_3}$。

在直线 $x=w$ 上有 $k_4$ 个点 $(w,y_1),(w,y_2),\cdots,(w,y_{k_4})$，保证 $y_1<y_2<\cdots<y_{k_4}$。

你需要找到一条直线上的任意两点和另一条直线上的任意一点，使得构成的三角形面积最大。数据保证每条直线上至少有 $2$ 个点。

输出最大三角形面积的 $2$ 倍，也就是计算三角形面积不需要除以 $2$。

输入格式

第一行一个整数 $t(1\le t\le 10^4)$，代表数据组数。

对于每一组数据：

第一行两个整数 $w,h(3\le w,h\le 10^6)$。

输出格式

输出每一组数据的能组成的最大三角形的面积的$2$倍。数据保证最后的结果是整数。

样例

3
5 8
2 1 2
3 2 3 4
3 1 4 6
2 4 5
10 7
2 3 9
2 1 7
3 1 3 4
3 4 5 6
11 5
3 1 6 8
3 3 6 8
3 1 3 4
2 2 4

25
42
35