AT_2_stpc2025_2_g.Team Division

给定正整数 $A, B, L, R$。

对于 $x = L, L+1, \dots, R$，定义 $f(x)$ 为如下问题的答案：

有一次程序设计竞赛，有 $x$ 名选手参加。

现需将这 $x$ 名选手分成若干支每支为 $A$ 人或 $B$ 人的队伍，每位选手必须恰好分入一支队伍。

求所有可能分组方式下，队伍的最小数量。如果无法完成分组，则答案为 $10^{100}$。

请你计算 $\displaystyle\max_{L \le x \le R} f(x)$。如果最大值为 $10^{100}$，请输出 $-1$。

有 $T$ 组测试数据，对每组分别输出结果。

输入格式如下：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

其中，$\mathrm{case}_i$ 表示第 $i$ 组测试数据。每组测试数据输入一行，包含 $A\ B\ L\ R$。

对于每组测试数据，输出一行答案。

样例解释 1

对于第一组数据，当参与人数为 $1$ 时，无法分成 $2$ 人或 $3$ 人队伍。

对于第二组数据，当参与人数为 $19$ 时，可以分成 $3$ 个 $3$ 人队伍和 $2$ 个 $5$ 人队伍，此时总队数为 $5$。对于所有 $10$ 到 $20$ 的人数，都可以分成不超过 $5$ 个队伍，所以答案为 $5$。

数据范围

• 所有输入均为整数
• $1 \leq T \leq 10^5$
• $1 \leq A, B \leq 10^9$
• $1 \leq L \leq R \leq 10^{18}$

由 ChatGPT 5 翻译