思路

• 设不小于 $l$ 的第一个满足同余的数为 $f$。可用如下任一等价形式求 $f$：

  • $f = l + \big((x - l) \bmod k\big)$，其中取值为 $0 \ldots k-1$ 的非负余数；
  • $f$ = $\left\lceil \dfrac{l - x}{k} \right\rceil \cdot k$ + $x$。

• 若 $f > r$，答案为 $0$，否则

$\text{ans}$ = $\left\lfloor \dfrac{r - f}{k} \right\rfloor$ + $1$

题目内容

游游有四个整数 $l,r,k,x$，求区间 $[l,r]$ 中有多少个整数 $i$ 满足：$i(mod$ $k)=x$ 。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T (1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下：

在一行上输入四个整数 $l,r,k,x (1≤l≤r≤10^9; 1≤k≤10^9; 0≤x≤k−1)$，表示查询的区间、模数、余数。

输出描述

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

样例1

输入

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

输出

3
4
57257