# Try Copying Again

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