#include <stdio.h>

__int128 generalized_floor_sum(long long n, long long m, long long a, long long b, __int128 p, __int128 q, __int128 r)
{
	if (n == 0) return 0;
	if (b >= m) return generalized_floor_sum(n, m, a, b % m, p, q, r + q * (b / m)) + p * (b / m) * n * (n - 1) / 2 + q * (b / m) * (b / m + 1) / 2 * n + r * (b / m) * n;
	if (a == 0) return 0;
	if (a >= m) return generalized_floor_sum(n, m, a % m, b, p + q * (a / m), q, r) + p * (a / m) * n * (n - 1) * (n * 2 - 1) / 6 + q * (a / m) * ((__int128)(a / m) * n * (n - 1) * (n * 2 - 1) / 6 + n * (n - 1) / 2) / 2 + r * (a / m) * n * (n - 1) / 2;
	
	long long y = (a * (n - 1) + b) / m;
	if (y == 0) return 0;
	return generalized_floor_sum(y, a, m, a * n - m * y + b, -q, -p, p * n + q * y + r);
}

__int128 generalized_floor_sum_naive(int n, int m, int a, int b, int p, int q, int r)
{
	int k, l;
	__int128 ans = 0;
	for (k = 0; k < n; k++) for (l = 1; l <= (a * k + b) / m; l++) ans += (long long)p * k + (long long)q * l + r;
	return ans;
}

long long solve(int N, int M, int X, int Y)
{
	return generalized_floor_sum(N, M, X, Y, 1, 0, 0) * 2 - generalized_floor_sum(N, M, X, Y, 0, 0, 1) * (N - 1) - generalized_floor_sum(N, M, X, 0, 0, 0, 1) * N + generalized_floor_sum(N, M, X, 0, 1, 0, 0);
}

int main()
{
	int T, N, M, X, Y;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d", &N, &M, &X, &Y);
		printf("%lld\n", solve(N, M, X, Y));
	}
	fflush(stdout);
	return 0;
}