--[[------------------------------------------------------------------------]]--
local function floor_sum(elm_num, div_num, mul_num, add_num)
	local ans = 0
	if mul_num >= div_num then
		ans = ans + (elm_num - 1) * elm_num * (mul_num // div_num) // 2
		mul_num = mul_num % div_num
	end
	if add_num >= div_num then
		ans = ans + elm_num * (add_num // div_num)
		add_num = add_num % div_num
	end

	local y_max = (mul_num * elm_num + add_num) // div_num
	local x_max = (y_max * div_num - add_num)
	if y_max == 0 then
		return ans
	else
		ans = ans + (elm_num - (x_max + mul_num - 1) // mul_num) * y_max
		ans = ans + floor_sum(
			y_max, mul_num, div_num,
			(mul_num - x_max % mul_num) % mul_num, ans
		)
		return ans
	end
end
--[[------------------------------------------------------------------------]]--

local read = io.read
local t = read("n")

local out_t = {}
for i = 1, t do
	out_t[i] = floor_sum(read("n", "n", "n", "n"))
end
print(table.concat(out_t, "\n"))
