对于任意两个正整数 $a$ 和 $b$，定义函数 $\texttt{gen_string}(a,b)$ 如下面的 Python 代码所示：

def gen_string(a: int, b: int):
    res = ""
    ia, ib = 0, 0
    while ia + ib < a + b:
        if ia * b <= ib * a:
            res += '0'
            ia += 1
        else:
            res += '1'
            ib += 1
    return res

等价的 C++ 代码为：

string gen_string(int64_t a, int64_t b) {
    string res;
    int ia = 0, ib = 0;
    while (ia + ib < a + b) {
        if ((__int128)ia * b <= (__int128)ib * a) {
            res += '0';
            ia++;
        } else {
            res += '1';
            ib++;
        }
    }
    return res;
}

当循环终止时，$ia$ 将等于 $a$，$ib$ 将等于 $b$，因此该函数返回一个长度为 $a+b$ 的位串，其中恰好包含 $a$ 个 $0$ 和 $b$ 个 $1$。例如，$\texttt{gen_string}(4,10)=01110110111011$。

如果存在正整数 $x$ 和 $y$ 使得 $s=\texttt{gen_string}(x,y)$，则称位串 $s$ 为 good。给定两个正整数 $A$ 和 $B$ ($1\le A,B\le 10^{18}$)，你的任务是计算 $\texttt{gen_string}(A,B)$ 的 good 前缀的数量。例如，$\texttt{gen_string}(4,10)$ 有 $6$ 个 good 前缀：

x = 1 | y = 1 | gen_string(x, y) = 01
x = 1 | y = 2 | gen_string(x, y) = 011
x = 1 | y = 3 | gen_string(x, y) = 0111
x = 2 | y = 5 | gen_string(x, y) = 0111011
x = 3 | y = 7 | gen_string(x, y) = 0111011011
x = 4 | y = 10 | gen_string(x, y) = 01110110111011

输入格式

第一行包含一个整数 $T$ ($1\le T\le 10$)，表示独立测试用例的数量。

接下来的 $T$ 行，每行包含两个整数 $A$ 和 $B$。

输出格式

对于每个测试用例，输出一行答案。

样例

样例输入 1

6
1 1
3 5
4 7
8 20
4 10
27 21

样例输出 1

1
5
7
10
6
13

子任务

• 输入 2: $A,B\le 100$
• 输入 3: $A,B\le 1000$
• 输入 4-7: $A,B\le 10^6$
• 输入 8-13: 所有答案均不超过 $10^5$。
• 输入 14-21: 无额外限制。

题目来源：Benjamin Qi