Bella Ciao!

It's evening 10:58, it was a fruitful day which is common nowadays, given the reason I am not going to the college, so getting around 7 hours extra which I am utilizing for completing my Networking Lectures and also I am working on Web Scraping through Python... talking of that there is a really disgusting problem for scraping stuff from Google specially when that is a type that Google generates differently for each user because then we cannot get the original response that we are seeing while normal browsing and we get a whole different lot of html code. Even with the same queries and even after specifying the location I am not getting the required stuff, maybe that's because of the use of Scraper or that they determine location based on the ip of the network. Well, apart from this the good news is that I also got banned from some sites for Scraping lots of jpegs from their databases, but I don't understand that why do they do this I mean a bit of scraping won't bring down their servers would they. 

The first time that I got a 403 forbidden, I continued with my Firefox, eventually because I understood that they identify source of the Scraper on the basis of the Browser, so after this I got to Google Chrome and now I am out of Browsers, but eventually I observed that I can browse them through normal browsing it's just that I am banned from scraping on their webs, well, maybe that would be temporary or maybe not, and also I am going to try again with a different IP and then with a different MAC, you know, I am not gonna leave them... ;)

For today's problem, this is fairly Easy one and also this will require some of your Pattern Recognition skills of some Series' that we all have studied and also this makes sense now, that why were we studying all those things in our School Time.

Well the Problem Statement is quite direct and simple to understand, try to find a solution which gives O(1) time Complexity but you can also go with a Looping Solution, that is good for a start but will fail the Second Sub-Task.

Problem Statement:-

Chef is planning a heist in the reserve bank of Chefland. They are planning to hijack the bank for $�$ days and print the money. The initial rate of printing the currency is $�$ dollars per day and they increase the production by $�$ dollars after every interval of $�$ days. For example, after $�$ days the rate is $�+�$ dollars per day, and after $2�$ days the rate is $�+2�$ 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 $�$, the number of test cases. Then the test cases follow.
• Each test case contains a single line of input, four integers $�,�,�,�$.

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

###Constraints

• $1\le �\le 10^5$
• $1\le �\le �\le 10^6$
• $1\le �,�\le 10^6$

###Subtasks Subtask #1 (15 points): $�\le �\le 100$

Subtask #2 (85 points): original constraints

Sample 1:

Input

Output

3
2 1 1 1
3 2 1 1
5 2 1 2

3
4
13

Explanation:

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.

Explanation:-

Simply, for this Problem we can either use the simple Arithmetic Formula and get the summation. After which we will also have to calculate the amount for the left days which are not considered in the AP, we will get those number of days by using the modulo operator and also we can calculate the end value of Rate of Money per Day( Here it is end_rate). We will get the answer by summing these two values. Apart from this, we can also see a pattern by separating the values of the summation and we will get the Series of First N Natural Numbers, so for that we can use their formula, and using this we will come across a formula which will also work the same just be sure that you use the Floor Division operator and not the normal division operator bcz that can lead to problems in some of the Test Cases.

Code Implementation:-

for _ in range(int(input())):

    D,d,p,q=map(int,input().split())

    total_cycles=(D//d)

    rem_days=D%d

    end_rate= p+q*total_cycles

    # My own formula, when we separate the terms, using the formula-

    # Summation of N first Natural Numbers

    amount=d*( p*total_cycles +  q*( (total_cycles-1)*total_cycles)//2)

    # Using the Arithmetic Progression Formula--> n/2(2a+(n-1)d),

    # Where, a is the first term of AP here p, and d is the common difference here q

    # amount=d*( (total_cycles*(2*p + (total_cycles-1)*q))//2  )

    rem_amount=rem_days*end_rate

    print(int(amount+rem_amount))