당구

길이가 $n$, 너비가 $m$인 당구대가 있다.

당구공 하나가 한 모서리에서 $45$도 각도로 움직이기 시작한다. 공이 언제 출발한 모서리로 다시 돌아오는지 구하라.

형식적으로 말하면, $n$과 $m$이 주어졌을 때 아래 함수의 반환값을 구해야 한다.

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;
}

첫 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 10^5$). 이후 각 테스트 케이스는 정수 $n$과 $m$이 한 줄에 주어진다 ($2 \le n, m \le 10^9$).

각 테스트 케이스마다 답을 한 줄에 출력한다.