def floor_linear_sum(n,m,a,b):

    res = 0

    if a >= m:

        res += (n-1)*n*(a//m)//2

        a %= m

    if b >= m:

        res += n * (b//m)

        b %= m

    y_max = (a*n+b)//m



    while y_max:

        x_max = y_max*m-b

        res += (n - (x_max + a - 1)//a)*y_max

        n,m,a,b = y_max, a, m, (a-x_max)%a

        if a >= m:

            res += (n-1)*n*(a//m)//2

            a %= m

        if b >= m:

            res += n * (b//m)

            b %= m



        y_max = (a*n+b)//m

    return res



T = int(eval(input()))

for _ in range(T):

    print((floor_linear_sum(*list(map(int,input().split())))))

def floor_linear_sum(n,m,a,b):

    res = 0

    while True:

        if a >= m:

            res += (n-1)*n*(a//m)//2

            a %= m

        if b >= m:

            res += n * (b//m)

            b %= m



        y_max = (a*n+b)//m

        if y_max == 0:

            return res

        x_max = y_max*m-b

        res += (n - (x_max + a - 1)//a)*y_max

        n,m,a,b = y_max, a, m, (a-x_max)%a



T = int(eval(input()))

for _ in range(T):

    print((floor_linear_sum(*list(map(int,input().split())))))

def floor_linear_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    while y_max:
        x_max = y_max * m - b
        res += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (a - x_max) % a
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            res += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
    return res


T = int(eval(input()))
for _ in range(T):
    print((floor_linear_sum(*list(map(int, input().split())))))

def floor_linear_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            res += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        if y_max == 0:
            return res
        x_max = y_max * m - b
        res += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (a - x_max) % a


T = int(eval(input()))
for _ in range(T):
    print((floor_linear_sum(*list(map(int, input().split())))))

-    if a >= m: -        res += (n - 1) * n * (a // m) // 2 -        a %= m -    if b >= m: -        res += n * (b // m) -        b %= m -    y_max = (a * n + b) // m -    while y_max: -        x_max = y_max * m - b -        res += (n - (x_max + a - 1) // a) * y_max -        n, m, a, b = y_max, a, m, (a - x_max) % a +    while True: -    return res +        if y_max == 0: +            return res +        x_max = y_max * m - b +        res += (n - (x_max + a - 1) // a) * y_max +        n, m, a, b = y_max, a, m, (a - x_max) % a