In this problem, you should process T testcases.  For each testcase, you are given four integers N, M, A, B.  Calculate \sum_{i = 0}^{N - 1} floor((A \times i + B) / M).
def solve(n,m,a,b):
    ans = 0
    lim = (a*n+b)//m
    
    for i in range(1,lim+1):
        l = (i*m-b+a-1)//a
        r = (i*m+m-b-1)//a

        ans += (min(r,n-1)-l+1)*i

    return ans

def main():
    t = int(input())
    while t>0:
        n,m,a,b = map(int, input().split(' '))
        print(solve(n,m,a,b))
        t-=1

if __name__ == "__main__":
    main()

#     ans = 0

    

#         l = (i*m-b+a-1)//a
#         r = (i*m+m-b-1)//a

#         ans += (min(r,n-1)-l+1)*i

#     return ans

def floor_sum(n, m, a, b):
    ans = 0

    # (a*i+b)//m
    
    if a>=m:
        ans += n*(n-1)*(a//m)//2
        a %= m


    
    if b>=m:
        ans += n*(b//m)
        b %= m

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

    if yn == 0:
        return ans 

    x_least = (yn * m - b) #the first x for which y(x) == yn ,'x_least' refers to the val a*x.

    l = (x_least+(a-1))//a
    r = n-1 

    return ans + (r-l+1)*yn + floor_sum(yn, a, m, (a-x_least%a)%a)
    '''
    #r+1 as we pass the element that does not belong in the range.

    '''
def main():
    t = int(input())
    while t>0:
        n,m,a,b = map(int, input().split(' '))
        # print(solve(n,m,a,b))
        print(floor_sum(n,m,a,b))
        t-=1

if __name__ == "__main__":
    main()




#left code
    # ans += (r-l+1)*yn  #if ans was not returned then this implies y(n) == y(n-1) == yn. element in window [l...r] have y(x) = yn
    # ans += floor_sum(yn, a, m, (a-x_least%a)%a)