配点 : 100 点
問題文
正整数 A, B, L, R 。 对于
x = L, L+1, \dots, R 关于 ,请回答以下问题 f(x) 。
将举办编程竞赛。参赛者 x 有人。
x 将人的竞技者 A 人或 B 人分成几个队伍。每个运动员必须恰好 1 个队伍。
此时,请求队伍数的最小値。但是,如果无法分队,请求答案为 10^{100} 。
\displaystyle\max_{L \le x \le R} f(x) 。但是,当答案为 10^{100} 时,-1 。
T 给出若干测试用例,请分别求出答案。
制約
- 所有输入均为整数
- 1 \leq T \leq 10^5
- 1 \leq A, B \leq 10^9
- 1 \leq L \leq R \leq 10^{18}
入力
输入按以下格式给出。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里,\mathrm{case}_i 是 您也可以写 i 个测试用例。每个测试用例均按以下格式给出。
A B L R
出力
T 个测试用例的答案请以换行分隔输出。
入力例 1
3 3 2 1 7 3 5 10 20 37 518946 448700728 617638174
出力例 1
-1 5 520098
关于第一个案例,当参加的大学生人数为 1 人时,2 人队伍也好,3 人队伍也好,都无法分组。
2 关于第一个案例,当参加的大学生人数为 19 人时,3 人员团队 3 津托 5 人员团队 2 分成是最合适的,此时,总队伍数为 5 。在参加大学生人数少于 10 人以上 20 人的任何场合,也可以分成少于5 个的团队,所以答案是 5 。 对于