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

    res = 0

    if b >= m:

        res += n * (b // m)

        b %= m

    while True:

        if a >= m:

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

            a %= 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.readline



for i in range(int(eval(input()))):

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

    print((floor_sum(n, m, a, b)))
# 一番早いのを写経したものを弄ってアルゴリズム勉強のための試し打ち中



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

    res = 0

    if b >= m:

        res += n * (b // m)

        b %= m

    while True:

        if a >= m:

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

            a %= 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 = [''] * 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
    if b >= m:
        res += n * (b // m)
        b %= m
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= 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.readline
for i in range(int(eval(input()))):
    n, m, a, b = list(map(int, input().split()))
    print((floor_sum(n, m, a, b)))

# 一番早いのを写経したものを弄ってアルゴリズム勉強のための試し打ち中
def floor_sum(n, m, a, b):
    res = 0
    if b >= m:
        res += n * (b // m)
        b %= m
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= 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 = [""] * 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)))

+# 一番早いのを写経したものを弄ってアルゴリズム勉強のための試し打ち中 -input = sys.stdin.readline -for i in range(int(eval(input()))): +input = sys.stdin.buffer.readline +T = int(eval(input())) +res = [""] * T +for i in range(T): -    print((floor_sum(n, m, a, b))) +    res[i] = str(floor_sum(n, m, a, b)) +print(("\n".join(res)))