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).
'''
Created on 2020/09/08

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  T=int(pin())
  for j in range(T):
    N,M,A,B=map(int,pin().split())
    ans=0
    for i in range(N):
      ans+=(A*i+B)//M
    print(ans)
  return
main()
'''
Created on 2020/09/08

@author: harurun
'''
def floor_sum(n,m,a,b):
  ans=0
  if a>=m:
    ans+=(n-1)*n*(a//m)//2
    a%=m
  if b>=m:
    ans+=n*(b//m)
    b%=m
  
  y_max=(a*n+b)//m
  x_max=y_max*m-b
  
  if y_max==0:
    return ans
  ans+=(n-(x_max+a-1)//a)*y_max
  ans+=floor_sum(y_max,a,m,(a-x_max%a)%a)
  return ans



def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  ansl=[]
  T=int(pin())
  for j in range(T):
    N,M,A,B=pin().split()
    ansl.append(str(floor_sum(int(N),int(M),int(A),int(B))))
  ans="\n".join(ansl)
  print(ans)
  return
main()