Với hai số nguyên dương $a$ và $b$ bất kỳ, định nghĩa hàm $\texttt{gen_string}(a,b)$ bằng đoạn mã Python sau:

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

Đoạn mã C++ tương đương:

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

Khi vòng lặp kết thúc, $ia$ sẽ bằng $a$ và $ib$ sẽ bằng $b$, nên hàm này trả về một xâu nhị phân có độ dài $a+b$ với đúng $a$ chữ số không và $b$ chữ số một. Ví dụ, $\texttt{gen_string}(4,10)=01110110111011$.

Gọi một xâu nhị phân $s$ là $\textbf{tốt}$ nếu tồn tại các số nguyên dương $x$ và $y$ sao cho $s=\texttt{gen_string}(x,y)$. Cho hai số nguyên dương $A$ và $B$ ($1\le A,B\le 10^{18}$), nhiệm vụ của bạn là tính số tiền tố tốt của $\texttt{gen_string}(A,B)$. Ví dụ, $\texttt{gen_string}(4,10)$ có $6$ tiền tố tốt:

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

Dữ liệu vào

Dòng đầu tiên chứa $T$ ($1\le T\le 10$), số bộ kiểm thử độc lập.

Mỗi dòng trong $T$ dòng tiếp theo chứa hai số nguyên $A$ và $B$.

Dữ liệu ra

Đáp án cho mỗi bộ kiểm thử trên một dòng riêng.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
5
7
10
6
13

Nhiệm vụ con

• Dữ liệu vào 2: $A,B\le 100$
• Dữ liệu vào 3: $A,B\le 1000$
• Dữ liệu vào 4–7: $A,B\le 10^6$
• Dữ liệu vào 8–13: Tất cả đáp án không vượt quá $10^5$.
• Dữ liệu vào 14–21: Không có giới hạn bổ sung.

Tác giả bài toán: Benjamin Qi