3096: Count

Let's define the function $f(x)$ to represent the largest integer that does not exceed $x$. In other words, we can use the following mathematical expression to express $f(x)$:
$$f(x)=\lfloor x \rfloor$$
For instance, $f(\frac{5}{2})=2$ and $f(3)=3$.


Now there are four integers $n, m, L, R$, We can use the following code to generate multiset $S$:

multiset<double> S;
for (int i = 1; i <= n; i++) {
    for (int j = L; j <= R; j++) {
        S.insert(1.0 * j / i);
    }
}

In other words:
$$S=\{ \frac{L}{1},\frac{L+1}{1} \cdots \frac{R}{1} \cdots \cdots \frac{L}{n},\frac{L+1}{n} \cdots \frac{R}{n} \}$$
Your task is to calculate how many elements in multiset S satisfy
$$f(\frac{m}{n})+f(x)=f(x+\frac{m}{n}),x \in S$$

Note that you need to solve $T$ test cases.

The first line contains an integer $T(1\leq T\leq 1000)$ —— the number of test cases you need to solve.

Each test case contains four integers $n, m, L$ and $R(1\leq n\leq 2*10^6, 1\leq m\leq 10^9, 1\leq L\leq R\leq 10^9)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2*10^6$.

For each test case, print the answer in one line.

3
2 1 5 7
2 4 5 7
3 10 5 7

4
6
8