任意の 2 つの正整数 $a$ と $b$ に対し、次の Python コードで関数 $\texttt{gen_string}(a,b)$ を定義します。

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$ 個の 0 と $b$ 個の 1 を含む長さ $a+b$ のビット列を返します。例えば、$\texttt{gen_string}(4,10)=01110110111011$ です。

正整数 $x$ と $y$ が存在して $s=\texttt{gen_string}(x,y)$ となるとき、ビット列 $s$ を「良い」（$\textbf{good}$）と呼びます。2 つの正整数 $A$ と $B$（$1\le A,B\le 10^{18}$）が与えられます。$\texttt{gen_string}(A,B)$ の良い接頭辞の個数を計算してください。例えば、$\texttt{gen_string}(4,10)$ には $6$ 個の良い接頭辞があります。

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$ 行のそれぞれには、2 つの整数 $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