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

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

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

• 巧克力的每个格子最多只能放置一个ㄱ骑士。
• 如果一个ㄱ骑士可以一步移动到某个格子，那么该格子上不能有另一个ㄱ骑士。
• 巧克力不能翻转或旋转。

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

输入格式

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

对于每个测试用例，在一行中给出巧克力的宽度 $X$、高度 $Y$，以及表示ㄱ骑士移动规则的 $x$ 和 $y$ 的值，各值之间用空格分隔。$(1 \le X, Y, x, y \le 50)$

输出格式

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

样例

输入样例 1

2
5 5 1 1
10 10 50 50

输出样例 1

15
100