package main

/*
#define true 1
#define false 0
#define bool int

// @param m `1 <= m`
// @return x mod m
long long safe_mod(long long x, long long m) {
	x %= m;
	if (x < 0) x += m;
	return x;
}

// Fast moduler by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
//

// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int barrett_mul(unsigned int _m, unsigned long long im, unsigned int a,
			 unsigned int b) {
	// [1] m = 1
	// a = b = im = 0, so okay

	// [2] m >= 2
	// im = ceil(2^64 / m)
	// -> im * m = 2^64 + r (0 <= r < m)
	// let z = a*b = c*m + d (0 <= c, d < m)
	// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
	// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1)
	// < 2^64 * 2
	// ((ab * im) >> 64) == c or c + 1
	unsigned long long z = a;
	z *= b;
#ifdef _MSC_VER
	unsigned long long x;
	_umul128(z, im, &x);
#else
	unsigned long long x =
	    (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
	unsigned int v = (unsigned int)(z - x * _m);
	if (_m <= v) v += _m;
	return v;
}

unsigned long long barrett_im(unsigned int m) {
	return (unsigned long long)(-1) / m + 1;
}

// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
long long pow_mod(long long x, long long n, int m) {
	if (m == 1) return 0;
	unsigned int _m = (unsigned int)(m);
	unsigned long long r = 1;
	unsigned long long y = safe_mod(x, m);
	while (n) {
		if (n & 1) r = (r * y) % _m;
		y = (y * y) % _m;
		n >>= 1;
	}
	return r;
}

// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
bool is_prime(int n) {
	if (n <= 1) return false;
	if (n == 2 || n == 7 || n == 61) return true;
	if (n % 2 == 0) return false;
	long long d = n - 1;
	while (d % 2 == 0) d /= 2;
	long long as[] = {2, 7, 61};
	for (int i = 0; i < sizeof(as) / sizeof(long long); i++) {
		long long a = as[i];
		long long t = d;
		long long y = pow_mod(a, t, n);
		while (t != n - 1 && y != 1 && y != n - 1) {
			y = y * y % n;
			t <<= 1;
		}
		if (y != n - 1 && t % 2 == 0) {
			return false;
		}
	}
	return true;
}

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
void inv_gcd(long long a, long long b, long long *g, long long *x) {
	a = safe_mod(a, b);
	if (a == 0) {
		*g = b;
		*x = 0;
		return;
	}

	// Contracts:
	// [1] s - m0 * a = 0 (mod b)
	// [2] t - m1 * a = 0 (mod b)
	// [3] s * |m1| + t * |m0| <= b
	long long s = b, t = a;
	long long m0 = 0, m1 = 1;

	while (t) {
		long long u = s / t;
		s -= t * u;
		m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

		// [3]:
		// (s - t * u) * |m1| + t * |m0 - m1 * u|
		// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
		// = s * |m1| + t * |m0| <= b

		long long tmp = s;
		s = t;
		t = tmp;
		tmp = m0;
		m0 = m1;
		m1 = tmp;
	}
	// by [3]: |m0| <= b/g
	// by g != b: |m0| < b/g
	if (m0 < 0) m0 += b / s;
	*g = s;
	*x = m0;
	return;
}

// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
int primitive_root(int m) {
	if (m == 2) return 1;
	if (m == 167772161) return 3;
	if (m == 469762049) return 3;
	if (m == 754974721) return 11;
	if (m == 998244353) return 3;
	int divs[20] = {};
	divs[0] = 2;
	int cnt = 1;
	int x = (m - 1) / 2;
	while (x % 2 == 0) x /= 2;
	for (int i = 3; (long long)(i)*i <= x; i += 2) {
		if (x % i == 0) {
			divs[cnt++] = i;
			while (x % i == 0) {
				x /= i;
			}
		}
	}
	if (x > 1) {
		divs[cnt++] = x;
	}
	for (int g = 2;; g++) {
		bool ok = true;
		for (int i = 0; i < cnt; i++) {
			if (pow_mod(g, (m - 1) / divs[i], m) == 1) {
				ok = false;
				break;
			}
		}
		if (ok) return g;
	}
}

*/
import "C"
import // do not insert blank lines above
(
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	nextToken func() ([]byte, error)
	nextLine  func() ([]byte, error)

	OutputBuffer *bufio.Writer

	OutputWriter io.Writer

	b []byte

	i int
)

// set up IO functions
func init() {

	SetInput(os.Stdin)
	SetOutput(os.Stdout)

}
func FloorSum(n, m, a, b int) int {
	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 += FloorSum(y_max, a, m, (a-x_max%a)%a)
	return ans
}

// Setup OutputBuffer and OutputWriter.
func SetOutput(w io.Writer) {
	OutputBuffer = bufio.NewWriter(w)
	OutputWriter = OutputBuffer
}

// Flushes OutputBuffer
func Flush() {
	if OutputBuffer != nil {
		OutputBuffer.Flush()
	}
}

// Returns true if c is a white space
func IsSpace(c byte) bool {
	switch c {
	case '\t', '\n', '\v', '\f', '\r', ' ':
		return true
	}
	return false
}

func IsNewLine(c byte) bool {
	switch c {
	case '\n', '\r':
		return true
	}
	return false
}

// Setup nextToken with input buffer.
func SetInput(r io.Reader) {
	buf := new(bytes.Buffer)
	var b []byte

	var i int
	rest := func() ([]byte, error) {
		for i < len(b) && IsSpace(b[i]) {
			i++
		}
		if i == len(b) {
			return nil, io.ErrUnexpectedEOF
		}
		j := i
		for i < len(b) && !IsSpace(b[i]) {
			i++
		}
		return b[j:i], nil
	}
	initial := func() ([]byte, error) {
		io.Copy(buf, r)
		b = buf.Bytes()
		nextToken = rest
		return rest()
	}
	nextToken = initial

	restLn := func() ([]byte, error) {
		for i < len(b) && IsNewLine(b[i]) {
			i++
		}
		if i == len(b) {
			return nil, io.ErrUnexpectedEOF
		}
		j := i
		for i < len(b) && !IsNewLine(b[i]) {
			i++
		}
		return b[j:i], nil
	}

	initialLn := func() ([]byte, error) {
		io.Copy(buf, r)
		b = buf.Bytes()
		nextLine = restLn
		return restLn()
	}
	nextLine = initialLn
}

// Reads next token and return it as []byte
func readb() []byte {
	b, err := nextToken()
	if err != nil {
		panic(err)
	}
	return b[:len(b):len(b)]
}

// Reads next token and return it as string
func reads() string {
	return string(readb())
}

// Reads next token and return it as int64
func readll() int64 {
	i, err := strconv.ParseInt(reads(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

// Reads next token and return it as int
func readi() int {
	return int(readll())
}

// Write args to OutputWriter without format
func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(OutputWriter, args...)
}
func main() {
	defer Flush()

	T := readi()
	for t := 0; t < T; t++ {
		N := readi()
		M := readi()
		A := readi()
		B := readi()
		println(FloorSum(N, M, A, B))
	}
}



Measured memory_bytes: 12832