module Math: sig
    val floor_sum: int -> int -> int -> int -> int
end = struct
    let rec floor_sum n m a b =
        let a, ans = if a >= m then a mod m,       (n - 1) * n * (a / m) / 2 else a, 0 in
        let b, ans = if b >= m then b mod m, ans +           n * (b / m)     else b, ans in
        let y_max = (a * n + b) / m in
        let x_max = y_max * m - b in
        if y_max = 0 then ans else
            let ans = ans + (n - (x_max + a - 1) / a) * y_max in
            ans + floor_sum y_max a m ((a - x_max mod a) mod a)
end ;;
Scanf.scanf "%d" (fun t ->
    for i = 1 to t do
        Scanf.scanf " %d %d %d %d" (fun n m a b ->
            Printf.printf "%d\n" @@ Math.floor_sum n m a b
        )
    done
)