import sys





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

    ans = n*(b//m)

    b %= m

    while True:

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

        a %= m

        if a*n+b < m:

            return ans

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

        b -= y_max*m  # now we have x_max = -(b//a)

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

        b %= a

        m, a, n = a, m, y_max





def main():

    t = int(sys.stdin.buffer.readline())

    for x in sys.stdin.buffer.readlines():

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

        res = floor_sum(n, m, a, b)

        print(res)





if __name__ == "__main__":

    main()

import sys





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

    ans = n*(b//m)

    b %= m

    while True:

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

        a %= m

        if a*n+b < m:

            return ans

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

        b -= y_max*m  # now we have x_max = -(b//a)

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

        b %= a

        m, a, n = a, m, y_max





def main():

    t = int(sys.stdin.buffer.readline())

    ans = [0]*t

    for i, x in enumerate(sys.stdin.buffer.readlines()):

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

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

    print(*ans, sep="\n")





if __name__ == "__main__":

    main()

import sys


def floor_sum(n, m, a, b):
    ans = n * (b // m)
    b %= m
    while True:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
        if a * n + b < m:
            return ans
        y_max = (a * n + b) // m
        b -= y_max * m  # now we have x_max = -(b//a)
        ans += (n + b // a) * y_max
        b %= a
        m, a, n = a, m, y_max


def main():
    t = int(sys.stdin.buffer.readline())
    for x in sys.stdin.buffer.readlines():
        n, m, a, b = list(map(int, x.split()))
        res = floor_sum(n, m, a, b)
        print(res)


if __name__ == "__main__":
    main()

import sys


def floor_sum(n, m, a, b):
    ans = n * (b // m)
    b %= m
    while True:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
        if a * n + b < m:
            return ans
        y_max = (a * n + b) // m
        b -= y_max * m  # now we have x_max = -(b//a)
        ans += (n + b // a) * y_max
        b %= a
        m, a, n = a, m, y_max


def main():
    t = int(sys.stdin.buffer.readline())
    ans = [0] * t
    for i, x in enumerate(sys.stdin.buffer.readlines()):
        n, m, a, b = map(int, x.split())
        ans[i] = floor_sum(n, m, a, b)
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

-    for x in sys.stdin.buffer.readlines(): -        n, m, a, b = list(map(int, x.split())) -        res = floor_sum(n, m, a, b) -        print(res) +    ans = [0] * t +    for i, x in enumerate(sys.stdin.buffer.readlines()): +        n, m, a, b = map(int, x.split()) +        ans[i] = floor_sum(n, m, a, b) +    print(*ans, sep="\n")