You are playing a game within an by
grid enclosed by walls, where rows are numbered
to
from top to bottom and columns are numbered
to
from left to right. Let
denote the position of the cell in row
and column
.
At the start of the game, a circular bullet with diameter equal to the size of each cell is inscribed in cell next to the left wall of the grid. The bullet is then shot from cell
and initially travels upwards and to the right with a constant speed that can be represented as a pair
, the number of seconds it takes to move
cell in the
and
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
direction. The
direction is unchanged.
- If the bullet hits the left or right wall, it ricochets and travels in the reverse
direction. The
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 test cases to ensure the integrity of your solution.
Constraints
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
Input Specification
The first line contains , the number of test cases to solve.
The next lines contain
space-separated integers
,
,
,
, and
.
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:
Comments