有一个长为 $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$)。

输出格式

对于每个测试用例，输出一行，包含一个整数，即问题的答案。

样例

样例输入 1

5
2 2
2 3
2 4
2 5
2 6

样例输出 1

4
12
8
20
12