fun main(args : Array<String>) {
    val t = readLine()!!.toInt()

    repeat(t) {
        val (n, m, a, b) = readLine()!!.split(" ").map { it.toLong() }
        println(floorSum(n, m, a, b))
    }
}

private fun floorSum(n: Long, m: Long, a: Long, b: Long): Long {
    var ans = 0L
    var aa = a
    var bb = b

    if (aa >= m) {
        ans += (n - 1) * n * (aa / m) / 2
        aa %= m
    }
    if (bb >= m) {
        ans += n * (bb / m)
        bb %= m
    }

    var yMax = (aa * n + bb) / m
    var xMax = (yMax * m - bb)

    if (yMax == 0L) return ans

    ans += (n - (xMax + aa - 1) / aa) * yMax
    ans += floorSum(yMax, aa, m, (aa - xMax % aa) % aa)

    return ans
}