题目描述

题目译自 USACO 2023 US Open Contest, Platinum Problem 2. Good Bitstrings

对于任意正整数 $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$ 是好的。给定两个正整数 $A$ 和 $B\ (1\le A,B\le 10^{18})$，你的任务是计算 \texttt{gen_string}(A,B) 的好前缀的数量。例如，\texttt{gen_string}(4,10) 有 $6$ 个好前缀，如下所示：

输入格式

第一行一个整数 $T\ (1\le T\le 10)$，表示互相独立的测试点个数。

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

输出格式

对于每个测试点，输出一行表示答案。

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

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 组数据：无附加限制