SOLVE

LATER

Profits by cars

/

You are a car seller. You have \(N\) cars and the profit for each of the cars is given by an array \(P\). The profit of cars are \(P_1,\ P_2,\ P_3,\ ...,\ P_N\). Since you got a huge profit in the last month so you decide to get \((N-1)\) more sets of such cars. You already have one car. Now, you have \(N^2\) cars. Basically, there are \(N\) number of cars of each profit such as \(N\) cars for profit \(P_1\), \(N\) cars of profit \(P_2\), and so on up to \(N\) cars of profit \(P_N\).

You can perform the following operations any number of times:

- If the last car is sold for profit \(P\), then you can sell a car for profit \(P_c >P \) .

**Note**: You can select a car of any profit in the first operation as there are no cars that are sold earlier.

Find out the maximum profit that you can make.

For example, \(N=4\) and prices are \(P_1,\ P_2,\ P_3,\ P_4\). Since \(N\) is **4**, therefore you can have four sets of cars and the prices are **\(P_1,\ P_2,\ P_3,\ P_4,\ P_1,\ P_2,\ P_3,\ P_4 ,\ P_1,\ P_2,\ P_3,\ P_4 ,\ P_1,\ P_2,\ P_3,\ P_4 \) .**

See the sample explanation for more details.

**Input format**

- The first line contains a single integer \(T\) denoting the number of test cases.
- The first line of each test case consists of an integer \(N\).
- The second line consists of \(N\) space-separated integers \(P_1,\ P_2,\ P_3,\ ...,\ P_N\)

**Output format**

For each test case, print a single integer denoting the maximum amount of profit that you can make.

**Constraints**

\(1 \leq T \leq 100\)

\(1\leq N\leq 100000\)

\(1\leq P_i<=1e9 \forall i \in [1,N]\)

Sum of \(N\) over all test cases does not exceed \(100000\)

Explanation

Since N=3 here jetha will have 3 sets of cars so cars he will have are of profit 1,2,3,1,2,3,1,2,3.

He has three choices for the first car so suppose that he sell a car with profit 3 then he can not perform any operation as there is no car with profit greater than 3.Profit he makes is 3.

Suppose he sells a car with profit 2.On next operation he can sell a car for profit 3 as 3 is only available choice.After that he has to terminate.Profit he can make is 2+3=5.

If he sells a car at profit 1 then on next he has two choices {2,3} if he sells the next car at 3.He has to terminate and the profit he makes is 4.While If he sells a car at profit 2 on next day he can make another move and sell the car at price 3 so total profit:1+2+3=6 which is highest he can make.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB