数字个数

题目描述

给定四个整数 $l, r, k, x$，请你计算在闭区间 $[l, r]$ 中，有多少个整数 $i$ 满足 $i \pmod k = x$。

输入格式

输入包含多组测试数据。

第一行输入一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 在一行上输入四个整数 $l, r, k, x$，分别表示查询的区间、模数和余数。

输出格式

对于每组测试数据，输出一行一个整数，表示符合条件的数字个数。

样例

样例输入

3
1 5 2 1
10 20 3 2
1 114514 2 0

样例输出

3
4
57257

提示

样例说明

• 对于第一组查询，在区间 $$ 中，满足 $i \pmod 2 = 1$ 的数有 $\{1, 3, 5\}$，共 3 个。
• 对于第二组查询，在区间 $$ 中，满足 $i \pmod 3 = 2$ 的数有 $\{11, 14, 17, 20\}$，共 4 个。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 10^4$
• $1 \le l \le r \le 10^9$
• $1 \le k \le 10^9$
• $0 \le x < k$