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

Coco wants to play a "G-Knight" game with this chocolate and several G-Knights. A G-Knight is a variation of a chess knight that can move $x$ squares to the right and $y$ squares down 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.

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

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

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

Input

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

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

Output

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

Examples

Input 1

2
5 5 1 1
10 10 50 50

Output 1

15
100