题目描述

この問題では一つの入力につきテストケースが $T$ 個与えられます。

整数 $A$, $B$, $C$, $D$ が与えられます。次の条件を満たす正整数 $i$ はいくつあるか求めてください。

• $A\ +\ B\ \times\ i$ 以上 $A\ +\ C\ \times\ i$ 以下の整数はいずれも、$D$ の倍数ではない。

なお、制約より答えが有限であることが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる。

$T$ $A_1$ $B_1$ $C_1$ $D_1$ $:$ $A_T$ $B_T$ $C_T$ $D_T$

输出格式

$T$ 行出力せよ。

$i$ 行目には、$i$ ケース目 ($A_i$, $B_i$, $C_i$, $D_i$) の答えを出力せよ。

题目大意

给定 $4$ 个整数 $A,B,C,D$，求有多少个正整数 $i$ 满足闭区间 $[A+Bi,A+Ci]$ 中没有 $D$ 的整倍数。

多组测试。

$T\leqslant10^4,1\leqslant A\lt D,0\leqslant B\lt C\lt D,2\leqslant D\leqslant 10^8$

2
3 1 2 5
99 101 103 105

1
25

提示

制約

• $1\ \leq\ T\ \leq\ 10{,}000$
• $1\ \leq\ A\ <\ D$
• $0\ \leq\ B\ <\ C\ <\ D$
• $2\ \leq\ D\ \leq\ 10^8$

Sample Explanation 1

$1$ ケース目の $(A\ +\ B\ \times\ i,\ A\ +\ C\ \times\ i)$ を列挙すると次のようになります。 $i\ =\ 3$ のみ条件を満たすことがわかります。 - $i\ =\ 1:\ (4,\ 5)$ - $i\ =\ 2:\ (5,\ 7)$ - $i\ =\ 3:\ (6,\ 9)$ - $i\ =\ 4:\ (7,\ 11)$ - $i\ =\ 5:\ (8,\ 13)$ - :