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):

    """

    returns sum((a*i+b)//m for i in range(n))

    """

    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

        nx_max = b - y_max*m

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

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



import sys

read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline



T = int(readline())

m = list(map(int,read().split()))

for t in zip(m,m,m,m):

    print((floor_linear_sum(*t)))

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):
    """
    returns sum((a*i+b)//m for i in range(n))
    """
    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
        nx_max = b - y_max * m
        res += (n + nx_max // a) * y_max
        n, m, a, b = y_max, a, m, nx_max % a


import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
T = int(readline())
m = list(map(int, read().split()))
for t in zip(m, m, m, m):
    print((floor_linear_sum(*t)))

+    """ +    returns sum((a*i+b)//m for i in range(n)) +    """ -        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 +        nx_max = b - y_max * m +        res += (n + nx_max // a) * y_max +        n, m, a, b = y_max, a, m, nx_max % a -T = int(eval(input())) -for _ in range(T): -    print((floor_linear_sum(*list(map(int, input().split()))))) +import sys + +read = sys.stdin.buffer.read +readline = sys.stdin.buffer.readline +T = int(readline()) +m = list(map(int, read().split())) +for t in zip(m, m, m, m): +    print((floor_linear_sum(*t)))