You are playing a game within an $(N+1)$ by $(M+1)$ grid enclosed by walls, where rows are numbered $0$ to $N$ from top to bottom and columns are numbered $0$ to $M$ from left to right. Let $(i,j)$ denote the position of the cell in row $i$ and column $j$.

At the start of the game, a circular bullet with diameter equal to the size of each cell is inscribed in cell $(D,0)$ next to the left wall of the grid. The bullet is then shot from cell $(D,0)$ and initially travels upwards and to the right with a constant speed that can be represented as a pair $(X,Y)$, the number of seconds it takes to move $1$ cell in the $x$ and $y$ direction, respectively.

Bullets ricochet off walls with the following rules:

• If the bullet hits the top or bottom wall, it ricochets and travels in the reverse $y$ direction. The $x$ direction is unchanged.
• If the bullet hits the left or right wall, it ricochets and travels in the reverse $x$ direction. The $y$ direction is unchanged.
• If the bullet hits two walls at a corner of the grid, both directions will reverse.
• If the bullet hits the same spot on a wall twice, it breaks the wall and exits the grid.

The game ends when the bullet has either returned back to its starting position or exited the grid by breaking a wall. Determine the length of the game, in seconds. Answer $T$ test cases to ensure the integrity of your solution.

Constraints

$1\le T\le {10}^5$

$1\le N,M\le {10}^6$

$1\le D\le N$

$1\le X,Y\le {10}^3$

Subtask 1 [30%]

$1\le T\le {10}^2$

$1\le N,M\le {10}^2$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains $T$, the number of test cases to solve.

The next $T$ lines contain $5$ space-separated integers $N$, $M$, $D$, $X$, and $Y$.

Output Specification

For each test case, output the number of seconds the game lasts.

Sample Input

1
3 6 1 1 2

Sample Output

12

Explanation for Sample

The bullet follows this path around the grid: