Với \(2\) số nguyên dương \(a\) và \(b\) bất kì. Ta định nghĩa hàm gen_string(a, b) bởi đoạn code 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

Tương đương với đoạn code C++ sau:

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

Một xâu nhị phân \(s\) được gọi là "tốt" nếu như tồn tại \(2\) số nguyên dương \(x\) và \(y\) sao cho \(s =\) gen_string(x, y). Bạn được cho \(2\) số \(A\) và \(B\) \((1 \le A, B \le 10^{18})\), bạn cần tính toán số xâu tiền tố "tốt" của xâu gen_string(A, B). Ví dụ, có \(6\) xâu tiền tố "tốt" của xâu gen_string(4, 10):

Input

• Dòng đầu tiên chứa số \(T\) \((T \le 10)\), chỉ số lượng test.
• \(T\) dòng tiếp theo, mỗi dòng chứa \(2\) số \(A\) và \(B\).

Output

• Gồm \(T\) dòng, mỗi dòng là đáp cho mỗi test.

Scoring

• Subtask \(1\): \(A, B \le 100\).
• Subtask \(2\): \(A, B \le 1000\).
• Subtask \(3\): \(A, B \le 10^6\).
• Subtask \(4\): Không có quá \(10^5\) xâu tiền tố tốt trong mỗi test.
• Subtask \(5\): Không có thêm ràng buộc.

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

1
5
7
10
6
13