問題文

正整数 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}

入力例 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 となります。