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

  r=0

  x,y,z=0,0,0

  while 1:

    if b>=m:

      x=b//m

    else:

      x=0

    if a>=m:

      y=a//m

    else:

      y=0

    r+=x*n

    b-=x*m

    r+=(y*n*(n-1))>>1

    a-=y*m

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

    if x==0:

      break

    y=b-x*m

    z=y//a

    r+=(n+z)*x

    a,b,n,m=m,y-z*a,x,a

  return r



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

  print((floor_sum(*list(map(int,input().split())))))
import sys

S=sys.stdin.readlines()

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

  r=0

  x,y,z=0,0,0

  while 1:

    if b>=m:

      x=b//m

    else:

      x=0

    if a>=m:

      y=a//m

    else:

      y=0

    r+=x*n

    b-=x*m

    r+=(y*n*(n-1))>>1

    a-=y*m

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

    if x==0:

      break

    y=b-x*m

    z=y//a

    r+=(n+z)*x

    a,b,n,m=m,y-z*a,x,a

  return r



for i in range(int(S[0])):

  print((floor_sum(*list(map(int,S[i+1].split())))))
def floor_sum(n, m, a, b):
    r = 0
    x, y, z = 0, 0, 0
    while 1:
        if b >= m:
            x = b // m
        else:
            x = 0
        if a >= m:
            y = a // m
        else:
            y = 0
        r += x * n
        b -= x * m
        r += (y * n * (n - 1)) >> 1
        a -= y * m
        x = (a * n + b) // m
        if x == 0:
            break
        y = b - x * m
        z = y // a
        r += (n + z) * x
        a, b, n, m = m, y - z * a, x, a
    return r


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

import sys

S = sys.stdin.readlines()


def floor_sum(n, m, a, b):
    r = 0
    x, y, z = 0, 0, 0
    while 1:
        if b >= m:
            x = b // m
        else:
            x = 0
        if a >= m:
            y = a // m
        else:
            y = 0
        r += x * n
        b -= x * m
        r += (y * n * (n - 1)) >> 1
        a -= y * m
        x = (a * n + b) // m
        if x == 0:
            break
        y = b - x * m
        z = y // a
        r += (n + z) * x
        a, b, n, m = m, y - z * a, x, a
    return r


for i in range(int(S[0])):
    print((floor_sum(*list(map(int, S[i + 1].split())))))

+import sys + +S = sys.stdin.readlines() + + -for i in range(int(eval(input()))): -    print((floor_sum(*list(map(int, input().split()))))) +for i in range(int(S[0])): +    print((floor_sum(*list(map(int, S[i + 1].split())))))