Coco has a rectangular chocolate bar with width $X$ and height $Y$. This chocolate bar is divided into $1 \times 1$ unit squares.

Coco wants to play a "G-Knight" game using this chocolate bar and several G-Knights. A G-Knight is a variation of a chess knight that can move $x$ squares horizontally and $y$ squares vertically, or $y$ squares horizontally and $x$ squares vertically in a single move. G-Knights are not obstructed by other pieces when moving. A G-Knight cannot move to a square that is outside the boundaries of the chocolate bar.

The G-Knight game is about placing as many G-Knights as possible on the chocolate bar while following these rules:

• At most one G-Knight can be placed on any single square of the chocolate bar.
• No G-Knight can be placed on a square that another G-Knight can reach in a single move.
• The chocolate bar cannot be flipped or rotated.

Calculate the maximum number of G-Knights Coco can place on the chocolate bar.

Input

The first line contains the number of test cases $T$. $(1 \le T \le 100\,000)$

For each test case, the width $X$ and height $Y$ of the chocolate bar, and the values $x$ and $y$ representing the movement rules of the G-Knight, are given in order on a single line, separated by spaces. $(1 \le X, Y, x, y \le 1\,000\,000\,000)$

Output

For each test case, output the maximum number of G-Knights that can be placed on the chocolate bar on a single line.

Examples

Input 1

2
5 5 1 1
6 6 1 2

Output 1

15
24