### Profits by cars

You can perform the following operations any number of times:

- If the last car is sold for profit , then you can sell a car for profit .

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, and prices are . Since is 4, therefore you can have four sets of cars and the prices are .

See the sample explanation for more details.

Input format

- The first line contains a single integer denoting the number of test cases.
- The first line of each test case consists of an integer .
- The second line consists of space-separated integers

Output format

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

Constraints

Sum of over all test cases does not exceed

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.

## Comments

## Post a Comment

Please give us your valuable feedback