Coco 有一块宽度为 $X$、高度为 $Y$ 的矩形巧克力。这块巧克力被划分为 $1 \times 1$ 大小的单位正方形。

Coco 想要用这块巧克力和若干个“ㄱ型骑士”来玩一个 ㄱ型骑士游戏。ㄱ型骑士是国际象棋中骑士（马）的一种变体，它每次可以移动到向左或向右 $x$ 格、向上或向下 $y$ 格的位置。ㄱ型骑士在移动时不会受到其他格子上棋子的阻碍。如果目标格子超出了巧克力的边界，则不能移动到该位置。

ㄱ型骑士游戏的目标是在巧克力上放置尽可能多的 ㄱ型骑士，并遵守以下规则：

• 巧克力的每个格子中最多只能放置一个 ㄱ型骑士。
• 任何一个 ㄱ型骑士一步能移动到的格子上不能有另一个 ㄱ型骑士。
• 巧克力不能被翻转或旋转。

请计算 Coco 最多可以在巧克力上放置多少个 ㄱ型骑士。

输入格式

第一行包含测试用例的数量 $T$。$(1 \le T \le 100\,000)$

对于每个测试用例，一行中给出四个由空格分隔的整数，分别表示巧克力的宽度 $X$、高度 $Y$，以及表示 ㄱ型骑士移动规则的 $x$ 和 $y$。$(1 \le X, Y, x, y \le 1\,000\,000\,000)$

输出格式

对于每个测试用例，在一行中输出可以在巧克力上放置的 ㄱ型骑士的最大数量。

样例

输入样例 1

2
5 5 1 1
6 6 1 2

输出样例 1

15
24