You are given N integers, A[1] to A[N]. You have to assign weights to these integers such that their weighted sum is maximized. The weights should satisfy the following conditions :

Each weight should be an positive integer.

W[1] = 1

W[i] should be in the range [2, W[i-1] + 1] for i > 1

Weighted sum is defined as S = A[1] * W[1] + A[2] * W[2] + ... + A[N] * W[N]

Input

There are multiple test cases. First line contains the number of test cases. Each test case consists of a single line containing N. This is followed by N lines, each containing A[i].

Output

For each test case, output one line - the maximum weighted sum.

Input

1
4
1
2
3
-4

Output

6

Explanation

The weights are 1,2,3,2

Constraints

N <= 10^6

| A[i] | <= 10^6

Total number of test cases is around 10.

Problem Setter: Rounak Tibrewal

Languages: C,C++,Java

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

Mode Judge

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