لأي عددين صحيحين موجبين $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$ أصفار و$b$ آحاد بالضبط. على سبيل المثال، $\texttt{gen_string}(4,10)=01110110111011$.

نسمي سلسلة البتات $s$ $\textbf{جيدة}$ إذا وُجد عددان صحيحان موجبان $x$ و$y$ بحيث $s=\texttt{gen_string}(x,y)$. عند إعطائك عددين صحيحين موجبين $A$ و$B$ ($1\le A,B\le 10^{18}$)، مهمتك هي حساب عدد البوادئ الجيدة للسلسلة $\texttt{gen_string}(A,B)$. على سبيل المثال، توجد $6$ بوادئ جيدة للسلسلة $\texttt{gen_string}(4,10)$:

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