题目描述

本题中，每组输入包含 $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$）的答案。

样例 1

输入

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$

样例解释 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)$
• ……

由 ChatGPT 4.1 翻译