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

    ret = 0

    while True:

        if a>=m:

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

            a%=m



        if b>=m:

            ret += n*(b//m)

            b%=m



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

        x = y*m-b



        if y==0:

            return ret



        ret += (n-(x+a-1)//a)*y

        n = y

        b = (a-x%a)%a

        m,a = a,m



T = int(eval(input()))



for i in range(T):

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

    print((FloorSum(n,m,a,b)))
"""

c_r_5さんの

https://atcoder.jp/contests/practice2/submissions/16626085

を参考に

"""



code = """

# distutils: language=c++

# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]

# cython: boundscheck=False

# cython: wraparound=False

cdef extern from "/opt/atcoder-stl/atcoder/math.hpp" namespace "atcoder" nogil:

    cdef long long floor_sum(long long n, long long m, long long a, long long b)



cpdef long long FloorSum(long long n, long long m, long long a, long long b):

    return floor_sum(n, m, a, b)

"""

import os,sys

if sys.argv[-1] == 'ONLINE_JUDGE':

    open('atcoder.pyx','w').write(code)

    os.system('cythonize -i -3 -b atcoder.pyx')

  

import sys

from atcoder import FloorSum



N = int(eval(input()))

for i in range(N):

    print((FloorSum(*list(map(int,input().split())))))
def FloorSum(n, m, a, b):
    ret = 0
    while True:
        if a >= m:
            ret += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        y = (a * n + b) // m
        x = y * m - b
        if y == 0:
            return ret
        ret += (n - (x + a - 1) // a) * y
        n = y
        b = (a - x % a) % a
        m, a = a, m


T = int(eval(input()))
for i in range(T):
    n, m, a, b = list(map(int, input().split()))
    print((FloorSum(n, m, a, b)))

"""
c_r_5さんの
https://atcoder.jp/contests/practice2/submissions/16626085
を参考に
"""
code = """
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
cdef extern from "/opt/atcoder-stl/atcoder/math.hpp" namespace "atcoder" nogil:
    cdef long long floor_sum(long long n, long long m, long long a, long long b)
cpdef long long FloorSum(long long n, long long m, long long a, long long b):
    return floor_sum(n, m, a, b)
"""
import os, sys

if sys.argv[-1] == "ONLINE_JUDGE":
    open("atcoder.pyx", "w").write(code)
    os.system("cythonize -i -3 -b atcoder.pyx")
import sys
from atcoder import FloorSum

N = int(eval(input()))
for i in range(N):
    print((FloorSum(*list(map(int, input().split())))))

-def FloorSum(n, m, a, b): -    ret = 0 -    while True: -        if a >= m: -            ret += (n - 1) * n * (a // m) // 2 -            a %= m -        if b >= m: -            ret += n * (b // m) -            b %= m -        y = (a * n + b) // m -        x = y * m - b -        if y == 0: -            return ret -        ret += (n - (x + a - 1) // a) * y -        n = y -        b = (a - x % a) % a -        m, a = a, m +""" +c_r_5さんの +https://atcoder.jp/contests/practice2/submissions/16626085 +を参考に +""" +code = """ +# distutils: language=c++ +# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl] +# cython: boundscheck=False +# cython: wraparound=False +cdef extern from "/opt/atcoder-stl/atcoder/math.hpp" namespace "atcoder" nogil: +    cdef long long floor_sum(long long n, long long m, long long a, long long b) +cpdef long long FloorSum(long long n, long long m, long long a, long long b): +    return floor_sum(n, m, a, b) +""" +import os, sys +if sys.argv[-1] == "ONLINE_JUDGE": +    open("atcoder.pyx", "w").write(code) +    os.system("cythonize -i -3 -b atcoder.pyx") +import sys +from atcoder import FloorSum -T = int(eval(input())) -for i in range(T): -    n, m, a, b = list(map(int, input().split())) -    print((FloorSum(n, m, a, b))) +N = int(eval(input())) +for i in range(N): +    print((FloorSum(*list(map(int, input().split())))))