题目描述

在这个问题中，你将会给出 $T$ 个测试用例的输入。

给定整数 $A$、$B$、$C$ 和 $D$，找出满足以下条件的正整数 $i$ 的数量：

• 在区间 $[A + B \\times i, A + C \\times i]$（包含两端）内的整数都不是 $D$ 的倍数。

我们可以证明在给定的约束下，这个数量是有限的。

约束条件

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

输入

输入以以下格式从标准输入给出：

$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$）。

示例输入 1

2
3 1 2 5
99 101 103 105

示例输出 1

1
25

第一个测试用例中 $(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)$
• $:$