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.
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
The first line contains , the number of test cases to solve.
The next lines contain space-separated integers , , , , and .
For each test case, output the number of seconds the game lasts.
1 3 6 1 1 2
Explanation for Sample
The bullet follows this path around the grid: