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: