Chocolate and ㄱ나이트 Game (Bitter)

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

Coco wants to play the ㄱ나이트 game with this chocolate and several ㄱ나이트 pieces. A ㄱ나이트 is a variant of the chess knight. In one move, it can go to a square $x$ squares to the right or left and $y$ squares up or down from its current square. A ㄱ나이트 ignores the other pieces while it moves. If the destination is outside the chocolate, the piece cannot move there.

The ㄱ나이트 game is played by placing as many ㄱ나이트 pieces as possible on the chocolate under these rules:

• A square can hold at most one ㄱ나이트.
• If a ㄱ나이트 can move in one move to a square, that square must not hold another ㄱ나이트.
• The chocolate cannot be flipped or rotated.

Find the maximum number of ㄱ나이트 pieces that Coco can place on the chocolate.

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

Each test case is given on one line with four integers $X$, $Y$, $x$, and $y$, separated by spaces. $(1\le X,Y,x,y\le 10^9)$

For each test case, print the maximum number of ㄱ나이트 pieces that can be placed on the chocolate, one per line.