AT_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 翻译