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

Time Limit: 6 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0