Billiard

Time limit1sMemory limit2048 MB

Summary

Given table dimensions n and m, the task is to count the steps a 45-degree billiard ball takes to return to the starting corner, for up to 10^5 queries.

Level: Medium6 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

A table has length $n$ and width $m$ .

A billiard ball starts moving from one corner at a 45-degree angle. When does the ball bounce back to where it started?

Formally, given $n$ and $m$ , compute the return value of the following function.

int64_t check(int n, int m) {
  int x = 0, y = 0;
  int dx = 1, dy = 1;
  int64_t t = 0;
  while (1) {
    if (x + dx < 0) dx *= -1;
    if (x + dx > n) dx *= -1;
    if (y + dy < 0) dy *= -1;
    if (y + dy > m) dy *= -1;
    x += dx;
    y += dy;
    ++t;
    if (x == 0 && y == 0) break;
  }
  return t;
}

Input

The first line contains an integer $t$ , the number of test cases ( $1 \le t \le 10^5$ ). Each test case is a single line with two integers $n$ and $m$ ( $2 \le n, m \le 10^9$ ).

Output

For each test case, output one line containing the answer.

Examples1

Example 1
Input
```
5
2 2
2 3
2 4
2 5
2 6
```
Expected output
```
4
12
8
20
12
```