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

        n = y_max

        b %= a

        m, a = a, m





input = sys.stdin.buffer.readline

t = int(eval(input()))

for _ in range(t):

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

    print((floor_sum(n, m, a, b)))

import sys

from numba import njit, i8





@njit((i8, i8, i8, i8), cache=True)

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





input = sys.stdin.buffer.readline

t = int(eval(input()))

for _ in range(t):

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

    print((floor_sum(n, m, a, b)))

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
        n = y_max
        b %= a
        m, a = a, m


input = sys.stdin.buffer.readline
t = int(eval(input()))
for _ in range(t):
    n, m, a, b = list(map(int, input().split()))
    print((floor_sum(n, m, a, b)))

import sys
from numba import njit, i8


@njit((i8, i8, i8, i8), cache=True)
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


input = sys.stdin.buffer.readline
t = int(eval(input()))
for _ in range(t):
    n, m, a, b = list(map(int, input().split()))
    print((floor_sum(n, m, a, b)))

+from numba import njit, i8 +@njit((i8, i8, i8, i8), cache=True) -        n = y_max -        m, a = a, m +        m, a, n = a, m, y_max