# Roadies

**Background**

Roadies 9 : Everything or Nothing. MTV "Roadies" back with season nine. The "Journey" has begun.In the first episode Ranvijay introduces a money task to all the selected roadies.The task is to cut a wooden log into smaller pieces,but what goes on in the world of roadies are its humorous twist and turn.

So the twist here is that, given a wooden log of length N inches and table of prices p(i) for i=1,2,3.....N (p(i) is the price of each log of length i), the roadies have to determine the maximum revenue r(N) obtained by cutting the log and selling the pieces.

So you have to help the roadies in this money task and credit their empty account with the maximum price obtained.

**Input**

First line contain number of test cases.

Each case consists of two lines.The first line contains N. The initial length of the wooden log.The second line contains N space seperated Integers p(i) ( where p(i) represents the price of each length of log ) .

**Constraints**

Number of Test Cases T , 1 < T <= 20

Length of wooden log N, 1 < N <= 10000

Max. Price of a single piece 1 <= p(i) < 1000000

**Output**

For each test case output on a single line the maximum revenue possible.

**Sample Input**

```
```

2

9

1 5 8 9 10 17 17 20 24

5

100 200 100 300 100

**Sample Output**

```
```

25

500

*Problem Setter : Vivek Bhatnagar*

**Languages:**C,C++,Java