Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fantastic Food

By olee12 · Limits 1s, 512 MB

As we all know that Alice and Bob just landed in Fantastic World and are going to stay for the next N days. It is high time for them to start a new life in Fantastic World and expand their business. Nowadays, Bob is quite busy with their public-private corporation business model expansion. On the other hand, Alice is doing all the other interesting tasks. But the most interesting task in Fantastic world is buying the food due to the very interesting tax system of Fantastic World.

Fantastic Food is the only food available in Fantastic World. The best thing about Fantastic Food is that it does not have any expiration date and the price of unit Fantastic Food on ith day is Pi FCU which is known in advance. FCU is the currency unit in Fantastic World. If Alice decides to buy Xi units on ith day, the total price she has to pay is defined by the equation Xi*Pi + Xi2. Here Xi2 is the complex tax she needs to pay.

Alice became very interested after knowing this interesting pricing system for Fantastic Food and started losing her interest for other interesting tasks. So she asked for your help, since you are the only person Alice know from Fantastic World. To help her, you have to find the minimum FCU she needs to spend to get Fantastic Food for the next N days. Note that, only one unit of Fantastic Food each is good enough for both Alice and Bob.

Input

Input begins with an integer, T (≤ 50), denoting the number of test cases. Each case starts with one integer, N (1 ≤ N ≤ 100000). Next line contains N integers separated by space and the i’th integer of this line represents the price Pi (1 ≤ Pi ≤ 10^9) of the Fantastic Food on the i’th day.

Output

For each case, print the case number and the minimum cost to buy Fantastic Food for N days.

Sample

InputOutput
1
2
1 1
Case 1: 4


Discussion
Statistics

17% Solution Ratio

fsshakkhorEarliest, 3w ago

zarif2Fastest, 0.1s

jaamilLightest, 2.6 MB

MU_ResplendenceShortest, 822B

Submit

Login to submit