Read problem statements in [Vietnamese],
[Bengali], [Mandarin Chinese], and [Russian] as well. 

Chef is planning a heist in the reserve bank of Chefland. They are planning to hijack the bank for $D$ days and print the money. The initial rate of printing the currency is $P$ dollars per day and they increase the production by $Q$ dollars after every interval of $d$ days. For example, after $d$ days the rate is $P+Q$ dollars per day, and after $2d$ days the rate is $P+2Q$ dollars per day, and so on. Output the amount of money they will be able to print in the given period.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
Each test case contains a single line of input, four integers $D, d, P, Q$. 

------ Output ------
For each test case, output in a single line the answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ d ≤ D ≤ 10^{6}$
$1 ≤ P, Q ≤ 10^{6}$

------ Subtasks ------
Subtask #1 (15 points): $d ≤ D ≤ 100$

Subtask #2 (85 points): original constraints

----- Sample Input 1 ------ 
3

2 1 1 1

3 2 1 1

5 2 1 2
----- Sample Output 1 ------ 
3

4

13
----- explanation 1 ------ 
Test Case $1$: 
- On the first day, the rate of production is $1$ dollar per day so $1$ dollar is printed on the first day.  
- On the second day, the rate of production is $1 + 1 = 2$ dollars per day so $2$ dollars are printed on the second day.
- The total amount of money printed in $2$ days is $1 + 2 = 3$ dollars.

Test Case $2$: 
- For the first two days, the rate of production is $1$ dollar per day so $1 \cdot 2 = 2$ dollars are printed on the first two days.  
- On the third day, the rate of production is $1 + 1 = 2$ dollars per day so $2$ dollars are printed on the third day.
- The total amount of money printed in $3$ days is $2 + 2 = 4$ dollars.

Test Case $3$: 
- For the first two days, the rate of production is $1$ dollar per day so $1 \cdot 2 = 2$ dollars are printed on the first two days.  
- On the next two days, the rate of production is $1 + 2 = 3$ dollars per day so $3 \cdot 2 = 6$ dollars are printed on the next two days.
- On the last day, the rate of production is $3 + 2 = 5$ dollars per day so $5$ dollars are printed on the last day.
- The total amount of money printed in $5$ days is $2 + 6 + 5 = 13$ dollars.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	quo = D // d
	rem = D % d
	ans = 0
	ans = quo * (2 * P + (quo - 1) * Q) // 2
	ans = ans * d
	a = (P + quo * Q) * rem
	ans += a
	print(int(ans))


T = int(input())
for _ in range(T):
	(D, d, P, Q) = map(int, input().split())
	n = D // d
	total = 0
	if n % 2 == 0:
		total += d * (n // 2) * (2 * P + (n - 1) * Q)
	else:
		total += d * n * (P + (n - 1) // 2 * Q)
	total += D % d * (P + n * Q)
	print(total)


def main():
	t = int(input())
	while t > 0:
		(D, d, P, Q) = map(int, input().split())
		n = D // d
		ans = n * P * d + Q * (n * (n - 1)) // 2 * d + D % d * (P + n * Q)
		print(ans)
		t -= 1
main()


for _ in range(int(input())):
	(D, d, p, q) = tuple(map(int, input().split()))
	n = D // d
	print(int(d * (2 * n * p + n * (n - 1) * q) // 2 + D % d * (p + n * q)))


for i in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	que = D // d
	rem = D % d
	ans = 0
	ans = que * (2 * P + (que - 1) * Q) // 2
	ans = ans * d
	a = (P + que * Q) * rem
	ans += a
	print(ans)


x = int(input())
ddr = []
for nnh in range(0, x):
	p = str(input())
	gh = p.split(' ')
	mm = []
	for bbv in gh:
		mm.append(int(bbv))
	ddr.append(mm)
for iir in ddr:
	x = iir[0] // iir[1]
	ltre = iir[0] % iir[1]
	ans = (iir[2] * x + iir[-1] * ((x - 1) * x // 2)) * iir[1] + (iir[2] + iir[-1] * x) * ltre
	print(ans)


for s in [*open(0)][1::1]:
	(D, d, P, Q) = map(int, s.strip().split())
	d1 = D // d
	print(d * (d1 * (2 * P + (d1 - 1) * Q)) // 2 + D % d * (P + d1 * Q))


for _ in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	R = D % d
	X = D // d
	print(P * X * d + Q * X * (X - 1) * d // 2 + R * (P + Q * X))


for _ in range(int(input())):
	(d, a, p, q) = map(int, input().split())
	ans = p * d
	i = d // a
	ans += a * i * (i - 1) * q // 2
	d = d % a
	ans += d * i * q
	print(ans)


for _ in range(int(input())):
	(D, d, p, q) = list(map(int, input().split()))
	quo = D // d
	ans = quo * (2 * p + q * (quo - 1)) // 2 * d
	rem = D % d
	ans += (p + q * quo) * rem
	print(ans)


for i in range(int(input())):
	(a, b, p, q) = map(int, input().split())
	print((a // b * p + a // b * (a // b - 1) // 2 * q) * b + (p + a // b * q) * (a % b))


for _ in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	(a, b) = (D // d, D % d)
	s = d * (a * P + a * (a - 1) * Q // 2) + b * (P + a * Q)
	print(int(s))


for _ in range(int(input())):
	(d, x, p, q) = map(int, input().split())
	print((d // x * p + d // x * (d // x - 1) // 2 * q) * x + (p + d // x * q) * (d % x))


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	(D, d, P, Q) = l
	h = D // d
	r = D % d
	ans = h * d * P + d * (h * (h - 1) // 2) * Q + r * (P + h * Q)
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(d, e, p, q) = map(int, input().split())
	t = d // e
	print(t * (2 * p + (t - 1) * q) // 2 * e + (p + t * q) * (d % e))


t = int(input())
while t:
	(d, a, p, q) = map(int, input().split(' '))
	cost = 0
	b = d // a
	r = d % a
	cost = a * b * p + a * b * (b - 1) * q // 2 + r * (p + b * q)
	print(int(cost))
	t -= 1


def prob(a, b, c, d):
	k = a // b
	print(a * (c + d * k) - b * d * k * (k + 1) // 2)
t = int(input())
for i in range(t):
	(a, b, c, d) = map(int, input().split())
	prob(a, b, c, d)


t = int(input())
for i in range(t):
	(D, d, p, q) = map(int, input().split())
	(n, rem) = (D // d, D % d)
	ans = n * p * d + q * d * (n - 1) * n // 2 + (p + n * q) * rem
	print(ans)


for i in range(int(input())):
	(D, d, p, Q) = map(int, input().split())
	c = D // d
	r = D % d
	t = p + c * Q
	amount = c * (2 * p + (c - 1) * Q) // 2 * d
	rem = r * t
	print(amount + rem)


for i in range(int(input())):
	(l, d, P, Q) = map(int, input().split())
	x = P * l
	l -= d
	n = l // d
	y = n * (n + 1) // 2 * Q * d
	z = (l // d + 1) * Q * (l - l // d * d)
	print(x + y + z)


from sys import stdin
l = []
for _ in range(int(stdin.readline())):
	(D, d, P, Q) = map(int, stdin.readline().split())
	intervals = D // d
	remaining = D % d
	amount = d * (intervals * (2 * P + (intervals - 1) * Q) // 2) + remaining * (P + intervals * Q)
	l.append(amount)
for i in l:
	print(i)


from math import factorial
for _ in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	x = P * D
	D -= d
	n = D // d
	y = n * (n + 1) // 2 * Q * d
	z = (D // d + 1) * Q * (D - D // d * d)
	print(x + y + z)


for _ in range(int(input())):
	(D, d, p, q) = map(int, input().split())
	ans = 0
	ans = ans + D * p
	D = D - d
	k = D // d
	rem = D - D // d * d
	ans = ans + d * q * (k * (k + 1)) // 2
	ans = ans + rem * (k + 1) * q
	print(ans)


cas = int(input())
for i in range(cas):
	(D, d, P, Q) = map(int, input().split())
	n = int(D // d)
	r = int(D % d)
	print(P * D + Q * (d * ((n * n - n) // 2) + n * r))


for _ in range(int(input())):
	(d, D, p, q) = map(int, input().split(' '))
	res = p * d + d // D * (d // D - 1) // 2 * q * D + d % D * (d // D) * q
	print(res)


for t in range(int(input())):
	(D, d, p, q) = map(int, input().split())
	Q = D // d
	r = D % d
	ans = Q * (2 * p + (Q - 1) * q) // 2
	ans *= d
	ans += (p + Q * q) * r
	print(ans)


t = int(input())
while t > 0:
	(D, d, p, q) = map(int, input().strip().split())
	(n, rem) = (D // d, D % d)
	ans = n * (2 * p + (n - 1) * q) // 2
	ans = ans * d
	ans += (p + q * n) * rem
	print(ans)
	t -= 1


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(D, d, p, q) = map(int, input().split())
	(n, rem) = (D // d, D % d)
	ans = n * p * d + q * d * (n - 1) * n // 2 + (p + n * q) * rem
	print(ans)


for _ in range(int(input())):
	(D, d, p, q) = map(int, input().split())
	(n, r) = (D // d, D % d)
	ans = n * (2 * p + (n - 1) * q) // 2
	ans *= d
	ans += (p + n * q) * r
	print(ans)


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	(D, d, p, q) = (l[0], l[1], l[2], l[3])
	c = 0
	c += D // d
	s = p * D + c * (c - 1) // 2 * q * d
	s += q * c * (D % d)
	print(s)


for _ in range(int(input())):
	(d, D, P, Q) = map(int, input().split(' '))
	p = 0
	p += d * P
	p += d // D * (d // D - 1) // 2 * Q * D
	p += d % D * (d // D) * Q
	print(p)


for _ in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	num = D // d
	rem = D % d
	answer = 0
	answer = num * (2 * P + (num - 1) * Q) // 2
	answer = answer * d
	aa = (P + num * Q) * rem
	answer += aa
	print(int(answer))


t = int(input())
for i in range(0, t):
	(D, d, P, Q) = list(map(int, input().split()))
	n = D // d
	res = D % d
	ans = 0
	ans = n * (2 * P + (n - 1) * Q) // 2
	ans = ans * d
	a = (P + n * Q) * res
	ans += a
	print(int(ans))


t = int(input())
for i in range(t):
	(D, d, P, Q) = map(int, input().split())
	money = 0
	fin = D // d
	money = (P * fin + Q * (fin - 1) * fin // 2) * d
	money += (D - fin * d) * (P + Q * fin)
	print(money)


t = int(input())
while t:
	(D, d, p, q) = [int(i) for i in input().split()]
	f = D // d
	l = D % d
	s = int(p * D + q * d * f * (f - 1) // 2 + q * f * l)
	print(s)
	t -= 1


for i in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	r = D // d
	r1 = D % d
	s = r * (2 * P + (r - 1) * Q) // 2
	s = s * d
	s += (P + r * Q) * r1
	print(int(s))


for _ in range(int(input())):
	(d, i, p, q) = map(int, input().split())
	import math
	a = math.floor(d / i)
	s = a * (2 * p + (a - 1) * q) * i
	s = s // 2
	s = s + (d - a * i) * (p + a * q)
	print(s)


import math
for x in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	n = math.floor(D / d)
	s = n * (2 * P + (n - 1) * Q) * d
	s = s // 2
	s = s + (D - n * d) * (P + n * Q)
	print(s)


for _ in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	x = D // d
	y = D % d
	total = D * P
	a = x * (x - 1)
	a = a // 2
	total += a * Q * d
	total += y * x * Q
	print(total)


t = int(input())
for _ in range(t):
	(D, d, P, Q) = list(map(int, input().split()))
	x = D // d
	r = D % d
	total = x * (2 * P + (x - 1) * Q) * d // 2 + r * (P + x * Q)
	print(total)


for i in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	n = D // d
	r = D % d
	sume = 0
	sume = n * (2 * P + (n - 1) * Q) // 2
	sume = sume * d
	a = (P + n * Q) * r
	sume += a
	print(int(sume))


t = int(input(''))
for i in range(t):
	(D, d, P, Q) = map(int, input().split())
	i = 1
	if D <= d:
		res = D * P
		print(res)
		continue
	else:
		s = D // d
		ans = int(s * P + (s - 1) * s * Q // 2) * d
		P = P + s * Q
		ans += int(P * (D % d))
		print(ans)


for _ in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	n = D // d
	if D % d:
		Last_prod = P * (D % d) + Q * (D % d) * n
	else:
		Last_prod = 0
	final_result = P * d * n + Q * d * (n * (n - 1)) // 2
	print(final_result + Last_prod)


for i in range(int(input())):
	(D, d, P, Q) = map(int, input().split())
	m = D // d
	v = m * P * d + Q * (m * (m - 1)) // 2 * d + D % d * (P + m * Q)
	print(v)


for _ in range(int(input())):
	(D, d, p, q) = [int(x) for x in input().split()]
	res = 0
	n = D // d
	r = D % d
	res = r * (p + n * q) + d * (n * p + q * (n * (n - 1)) // 2)
	print(res)


T = int(input())
for i in range(T):
	(D, d, P, Q) = map(int, input().split())
	R = D % d
	A = int(D / d)
	S = d * (A * P + Q * (A * (A - 1)) // 2) + R * (P + A * Q)
	print(int(S))


t = int(input())
while t != 0:
	(D, d, P, Q) = map(int, input().split())
	num = D // d
	rem = D % d
	ans = 0
	ans = num * (2 * P + (num - 1) * Q) // 2
	ans = ans * d
	a = (P + num * Q) * rem
	ans += a
	print(int(ans))
	t -= 1


from math import *
for _ in range(int(input())):
	(D, d, p, q) = map(int, input().split())
	r = D // d
	s = r * p * d + q * (r * (r - 1)) // 2 * d + D % d * (p + r * q)
	print(s)


t = input()
for c in range(0, int(t)):
	(D, d, P, Q) = map(int, input().split())
	num = D // d
	rem = D % d
	ans = 0
	ans = num * (2 * P + (num - 1) * Q) // 2
	ans = ans * d
	a = (P + num * Q) * rem
	ans += a
	print(int(ans))


T = int(input())
for case in range(T):
	(D, d, p, Q) = [int(tmp) for tmp in input().strip().split(' ')]
	n = D // d
	cost = D * p + n * Q * D - n * (n + 1) // 2 * Q * d
	print(cost)