题目描述

给定一个等差数列，其首项为 $a_1$，公差为 $d$。该数列中的任意一项都可以表示为 $a_1 + k \cdot d$ 的形式，其中 $k$ 为非负整数（即 $k \ge 0$）。因此，该数列的项依次为

现在给定一个闭区间 $[l, r]$，请你计算在该区间内，共有多少个数字属于这个等差数列。

输入格式

第一行包含一个整数 $T$ —— 表示测试用例的数量。

接下来 $T$ 行，每行包含四个正整数 $a_1, d, l, r$ —— 分别表示等差数列的首项、公差，以及查询区间的左边界和右边界。

输出格式

对于每个测试用例，输出一行一个整数，表示区间 $[l, r]$ 内属于该等差数列的数字个数。

样例输入 1

4
2 3 1 10
5 2 1 4
10 5 10 20
1000000000000000000 1000000000000000000 1 1000000000000000000

样例输出 1

3
0
3
1

说明

样例解释

• 在第一个测试用例中，$a_1 = 2, d = 3$，等差数列的项依次为 $2, 5, 8, 11, \dots$。在区间 $[1, 10]$ 中，属于该数列的数字有 $2, 5, 8$，共 $3$ 个。
• 在第二个测试用例中，$a_1 = 5, d = 2$，等差数列的项依次为 $5, 7, 9, \dots$。在区间 $[1, 4]$ 中没有任何数字属于该数列，因此输出 $0$。
• 在第三个测试用例中，$a_1 = 10, d = 5$，数列为 $10, 15, 20, 25, \dots$。区间 $[10, 20]$ 内有 $10, 15, 20$，共 $3$ 个。
• 在第四个测试用例中，等差数列的第一项即为 $10^{18}$，恰好在区间 $[1, 10^{18}]$ 的右边界上，因此共有 $1$ 个。

数据范围

• 对于所有测试点，保证 $1 \le T \le 10^3$。
• 对于每个测试用例，保证 $1 \le a_1, d \le 10^{18}$。
• 对于每个测试用例，保证 $1 \le l \le r \le 10^{18}$。