33396번 - Billiard 다국어

문제

There is a table with length $n$ and width $m$.

A billiard ball begins to move from one corner with an angle of 45ドル$ degrees.

When will the ball bounce back to where it starts?

Formally, you are given $n$ and $m,ドル and you need to calculate 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;
}

입력

The first line contains an integer $t,ドル the number of test cases (1ドル \le t \le 10^5$). The test cases follow.

Each test case is described by a single line containing two integers $n$ and $m$ (2ドル \le n, m \le 10^9$).

출력

For each test case, output a line containing one integer: the answer to the problem.

제한

힌트