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

    res = 0

    while True:

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

        a %= m

        res += n * (b // m)

        b %= m

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

        if y_max == 0: break

        x_max = y_max * m - b

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

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

    return res



import sys

input = sys.stdin.buffer.readline



T = int(eval(input()))

res = [None] * T



for i in range(T):

    n, m, a, b = list(map(int, input().split()))

    res[i] = str(floor_sum(n, m, a, b))



print(('\n'.join(res)))
def floor_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: break

        x_max = b - y_max * m

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

        n, m, a, b = y_max, a, m, x_max % a

    return res



import sys

input = sys.stdin.buffer.readline



T = int(eval(input()))

res = [None] * T



for i in range(T):

    n, m, a, b = list(map(int, input().split()))

    res[i] = str(floor_sum(n, m, a, b))



print(('\n'.join(res)))
def floor_sum(n, m, a, b):
    res = 0
    while True:
        res += (n - 1) * n * (a // m) // 2
        a %= m
        res += n * (b // m)
        b %= m
        y_max = (a * n + b) // m
        if y_max == 0:
            break
        x_max = y_max * m - b
        res += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, -x_max % a
    return res


import sys

input = sys.stdin.buffer.readline
T = int(eval(input()))
res = [None] * T
for i in range(T):
    n, m, a, b = list(map(int, input().split()))
    res[i] = str(floor_sum(n, m, a, b))
print(("\n".join(res)))

def floor_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:
            break
        x_max = b - y_max * m
        res += (n + x_max // a) * y_max
        n, m, a, b = y_max, a, m, x_max % a
    return res


import sys

input = sys.stdin.buffer.readline
T = int(eval(input()))
res = [None] * T
for i in range(T):
    n, m, a, b = list(map(int, input().split()))
    res[i] = str(floor_sum(n, m, a, b))
print(("\n".join(res)))

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