We will find an equivalent condition to \(k < (Ak+B) \bmod M\):

\[ \begin{aligned} &\phantom{\iff} k < (Ak+B) \bmod M\\ &\iff k+1 \le Ak+B-M\left\lfloor\frac{Ak+B}M \right\rfloor \\ &\iff \left\lfloor\frac{Ak+B}M \right\rfloor \le \frac{(A-1)k+(B-1)}M\\ &\iff \left\lfloor\frac{Ak+B}M \right\rfloor \le \left\lfloor\frac{(A-1)k+(B-1)}M\right\rfloor\\ \end{aligned} \]

In the last transformation, we use the fact that \(X \le x\) and \(X \le \left\lfloor x\right\rfloor\) are equivalent for any real number \(x\) and an integer \(X\).

Since \(\displaystyle \left\lfloor\frac{Ak+B}M \right\rfloor-\left\lfloor\frac{(A-1)k+(B-1)}M \right\rfloor\) takes only \(0\) or \(1\), the number of integers \(k\) satisfying the conditions can be represented as \(\displaystyle N-\sum_{k=0}^{N-1} \left(\left\lfloor\frac{Ak+B}M \right\rfloor-\left\lfloor\frac{(A-1)k+(B-1)}M \right\rfloor\right)\). This can be evaluated in \(O(\log M )\) using the floor sum algorithm.

The problem can be solved by appropriately implementing this algorithm. The complexity is \(O(\log M)\) per query.

Sample code (Python 3)

import sys
input = sys.stdin.readline

def floor_sum(n, m, a, b):
    a1, a2 = a // m, a % m
    s = n * (n - 1) // 2 * a1
    b1, b2 = b // m, b % m
    if a2 == 0:
        return s + b1 * n
    k = (a2 * (n - 1) + b2) // m
    return s + n * (k + b1) - floor_sum(k, a2, m, m + a2 - b2 - 1)

for _ in range(int(input())):
    n, m, a, b = map(int, input().split())
    print(n - floor_sum(n, m, a, b) + floor_sum(n, m, a - 1, b - 1))