問題文

$M$ 以下の正の整数のうちで $A$ の倍数または $B$ の倍数であるものが $N$ 個あるとして、それらを小さいものから順にすべて並べてできる数列 $X = (X_1, X_2, \ldots, X_N)$ を考えます。

$X_{i+1} - X_i = K$ を満たす整数 $i$（$1 \leq i \leq N - 1$）はいくつありますか？

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

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

それぞれのテストケースは次の形式で与えられます。

$M$ $A$ $B$ $K$

• 入力はすべて整数である
• $1 \leq T \leq 10^4$
• $1 \leq A < B \leq 10^9$
• $A \leq M \leq 10^{18}$
• $1 \leq K \leq 10^9$

出力

それぞれのテストケースについて、答えを出力してください。テストケースごとに改行してください。

サンプル

8
18 3 5 1
18 3 5 2
18 3 5 3
18 3 5 4
150 4 7 3
1000 10 20 10
1000000000000000000 999999999 1000000000 314159265
1000000000000000000 2 3 1

2
2
3
0
11
99
2
333333333333333334