AT_stpc2025_2_g Team Division

正整数 $ 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 $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ ここで、 $ \mathrm{case}_i $ は $ i $ 番目のテストケースを表す。各テストケースは以下の形式で与えられる。 > $ A $ $ B $ $ L $ $ R $

$ T $ 個のテストケースについて答えを改行区切りで出力せよ。

### Sample Explanation 1 最初のケースについて、参加人数が $ 1 $ 人の場合、 $ 2 $ 人チームにも、 $ 3 $ 人チームにも分けることはできません。 $ 2 $ つ目のケースについて、参加人数が $ 19 $ 人の場合、 $ 3 $ 人チーム $ 3 $ つと $ 5 $ 人チーム $ 2 $ つに分けるのが最適で、この時、合計チーム数は $ 5 $ となります。 参加人数が $ 10 $ 人以上 $ 20 $ 人以下のどの場合でも、 $ 5 $ 個以下のチームに分けることができるので、答えは $ 5 $ となります。 ### Constraints - 入力はすべて整数 - $ 1 \leq T \leq 10^5 $ - $ 1 \leq A, B \leq 10^9 $ - $ 1 \leq L \leq R \leq 10^{18} $